幸運的朋友
作法 : 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;
}
上一篇:班際籃球賽