摸索C語言 前身 : 摸索C語言 http://mypaper.pchome.com.tw/iustlovefish 現在即將就讀中興大學資訊科學與工程學系 XD

79愛的鼓勵 1訂閱站台

作法 : D&C 分而治之

假使要算出5^35次方

先將35做二進位制

=100011

將對應5^1 5^2 5^4 5^8 5^16 5^32

最後把有1的相乘 5^1 * 5^2 * 5^32 =5^32

一來次數就會減少很多

再來就必須用千進制來加速 才能得到  AC

程式碼2 : 採用億進制(捨去記憶體+快速度)

※　進位分開跑會比較快哦(2倍) ※因為被執行的次數差異,使得速度差很多

/******************************************************/

#include<stdlib.h>  
#include<stdio.h>  
int m_n[14][50000]={0},last[15]={0},ANS[50000]={0},i,k;  
int make(int n,int m)  
{  
    m_n[0][0]=m;  
    int a,b,c;  
    for(a=0;a<=n;a++) last[a]=0;   
    last[0]=2;  
    for(a=1;a<=n;a++)  
       {  
          for(b=0;b<=last[a-1];b++)  
             for(c=0;c<=last[a-1];c++)  
                {   
                 m_n[a][b+c]+=(m_n[a-1][b]*m_n[a-1][c]);  
                 m_n[a][b+c+1]+=(m_n[a][b+c]/1000);  
                 m_n[a][b+c]%=1000;   
                }   
          for(b=2*last[a-1]+1;b>=0;b--)  
             if(m_n[a][b]!=0)   
               {  
                 last[a]=b;  
              /*   for(c=b;c>=0;c--) 
                    printf("%d",m_n[a][c]);  
                 printf("\n");*/   
                 break;  
               }   
       }   
}   
int clear(int a,int lastA)  
{  
  int b,c;  
  for(b=0;b<=a;b++)  
     for(c=0;c<=last[b];c++)  
        m_n[b][c]=0;  
  for(b=0;b<=lastA;b++)  ANS[b]=0;   
}   
int DC(int n,int m)  
{  
   int s[100]={0},a,b,c,d,lastA=2;  
   s[0]=n;  
   for(a=0;a<100;a++)  
      if(s[a]>=2)   {s[a+1]+=(s[a]/2);s[a]%=2;}   
      else break;  
   make(a,m);   
   ANS[0]=1;   
   for(b=a;b>=0;b--)  
      if(s[b]==1)   
         {   
            int temp[50000]={0};   
            for(c=0;c<=last[b];c++)  
               for(d=0;d<=lastA;d++)  
                    temp[c+d]+=(ANS[d]*m_n[b][c]);   
            for(c=0;c<=last[b]+lastA+2;c++)  
                    {   
                    temp[c+1]+=(temp[c]/1000);  
                    temp[c]%=1000;   
                    ANS[c]=temp[c];  
                    }   
            for(c=last[b]+lastA+2;c>=0;c--)  
               if(ANS[c]!=0)  
                  {  lastA=c;  break;  }   
         }  
   int DCC[50000]={0},top=0;  
        
     for(b=0;b<=lastA;b++)  
         {  
            DCC[top++]=ANS[b]%10;  
            ANS[b]/=10;   
            DCC[top++]=ANS[b]%10;  
            ANS[b]/=10;   
            DCC[top++]=ANS[b]%10;  
         }  
     for(b=top;b>=0;b--)  
        if(DCC[b]!=0)   
           {  
             lastA=top;  
             for(c=b-i+1;c>=0&&c>=b-i-k+2;c--)  
                printf("%c",DCC[c]+48);  
                printf("\n");   
             break;  
           }   
     /*for(b=lastA;b>=0;b--)  
      printf("%d",ANS[b]); 
      printf("\n");*/ 
   clear(a,lastA);  
}  
main()  
{  
  int m,n,time=0;  
  while(scanf("%d %d %d %d",&m,&n,&i,&k)==4)  
        DC(n,m);   
  return 0;  
} 

 

/******************************************************/

#include<stdlib.h>        
#include<stdio.h>        
int last[15]={0},i,k;  
long long int m_n[14][15000]={0},ANS[15000]={0};  
int make(int n,int m)        
{        
    m_n[0][0]=m;        
    int a,b,c;        
    for(a=0;a<=n;a++) last[a]=0;         
    last[0]=2;        
    for(a=1;a<=n;a++)        
       {        
          for(b=0;b<=last[a-1];b++)        
             for(c=0;c<=last[a-1];c++)        
                 m_n[a][b+c]+=(m_n[a-1][b]*m_n[a-1][c]);        
          for(b=0;b<=2*last[a-1];b++)     
              {                      
                 m_n[a][b+1]+=(m_n[a][b]/100000000);        
                 m_n[a][b]%=100000000;         
              }     
          for(b=2*last[a-1]+1;b>=0;b--)        
             if(m_n[a][b]!=0)         
               {  last[a]=b;  break;   }         
       }         
}         
int clear(int a,int lastA)        
{        
  int b,c;        
  for(b=0;b<=a;b++)        
     for(c=0;c<=last[b];c++)        
        m_n[b][c]=0;        
  for(b=0;b<=lastA;b++)  ANS[b]=0;         
}         
int DC(int n,int m)        
{        
   int s[100]={0},a,b,c,d,lastA=2;        
   s[0]=n;        
   for(a=0;a<100;a++)        
      if(s[a]>=2)   {s[a+1]+=(s[a]/2);s[a]%=2;}         
      else break;        
   make(a,m);         
   ANS[0]=1;         
   for(b=0;b<=a;b++)        
      if(s[b]==1)         
         {         
            long long int temp[15000]={0};         
            for(c=0;c<=last[b];c++)        
               for(d=0;d<=lastA;d++)     
                    temp[c+d]+=(ANS[d]*m_n[b][c]);         
            for(c=0;c<=last[b]+lastA+2;c++)        
                    {         
                    temp[c+1]+=(temp[c]/100000000);        
                    temp[c]%=100000000;         
                    ANS[c]=temp[c];        
                    }         
            for(c=last[b]+lastA+2;c>=0;c--)        
               if(ANS[c]!=0)        
                  {  lastA=c;  break;  }         
         }        
    int DCC[50000]={0},top=0;        
              
     for(b=0;b<=lastA;b++)        
         {        
            DCC[top++]=ANS[b]%10;        
            ANS[b]/=10;         
            DCC[top++]=ANS[b]%10;        
            ANS[b]/=10;         
            DCC[top++]=ANS[b]%10;  
            ANS[b]/=10;         
            DCC[top++]=ANS[b]%10;  
            ANS[b]/=10;         
            DCC[top++]=ANS[b]%10;  
            ANS[b]/=10;         
            DCC[top++]=ANS[b]%10;  
            ANS[b]/=10;         
            DCC[top++]=ANS[b]%10;  
            ANS[b]/=10;         
            DCC[top++]=ANS[b]%10;  
         }        
     for(b=top;b>=0;b--)        
        if(DCC[b]!=0)         
           {        
             for(c=b-i+1;c>=0&&c>=b-i-k+2;c--)        
                printf("%c",DCC[c]+48);        
                printf("\n");         
             break;        
           }              
   clear(a,lastA);        
}        
main()        
{        
  int m,n,time=0;        
  while(scanf("%d %d %d %d",&m,&n,&i,&k)==4)        
        DC(n,m);         
  return 0;        
}