題目：http://acm.fzu.edu.cn/problem.php?pid=1759

也算是快速冪的一題了，只不過(guò)這里的指數(shù)B特別大。需要用到一個(gè)公式：

?A^x = A^(x % Phi(C) + Phi(C)) (mod C)，其中x≥Phi(C)

具體證明可見ac大神博客：http://hi.baidu.com/aekdycoin/item/e493adc9a7c0870bad092fd9。數(shù)論學(xué)得各種敗筆和急于求成，自己的理解就不談了～直接上代碼就是直接用到公式即可：

1 #include<iostream> 2 #include<cstdio> 3 #include<cmath> 4 #include<algorithm> 5 #include<cstring> 6 using namespace std; 7 char bb[1000005]; 8 __int64 euler(__int64 x){ 9 __int64 i, res = x; 10 for(i=2;i<(__int64)sqrt(x*10)+1;i++){// 11 if(x%i==0){ 12 res = res /i *(i-1); 13 while(x%i==0) x/=i; 14 } 15 } 16 if(x>1) res = res/x*(x-1); 17 return res; 18 } 19 __int64 quickpow(__int64 m, __int64 n, __int64 k){ 20 __int64 b = 1; 21 while(n>0){ 22 if(n&1){ 23 b = ((b%k)*(m%k))%k; 24 } 25 n = (n>>1); 26 m = ((m%k)*(m%k))%k; 27 } 28 return b; 29 } 30 int main(){ 31 __int64 a, c, b, phic, sum; 32 int i, j, k, l; 33 while(~scanf("%I64d",&a)){ 34 scanf("%s",bb); 35 scanf("%I64d",&c); 36 l = strlen(bb); 37 phic = euler(c); 38 if(l<=10){ 39 b = bb[0]-'0'; 40 for(i=1;i<l;i++){ 41 b = b*10 + (bb[i]-'0'); 42 } 43 if(b<phic){ 44 printf("%I64d\n",quickpow(a,b,c));continue; 45 } 46 } 47 b = 0ll; //求一個(gè)很大的數(shù)對(duì)一個(gè)數(shù)的模數(shù)的方法 48 for(i=0;i<l;i++){ 49 b = b*10 + (bb[i]-'0'); 50 while(b>=phic){ //while很重要！！！，防溢出 51 b -= phic; 52 } 53 /*if(b>=phic){ 54 b = b%phic; 55 }*/ 56 } 57 printf("%I64d\n",quickpow(a,b+phic,c)); 58 } 59 return 0; 60 }

還有一個(gè)09上海賽的題（hdu3221），大致也是那樣思路做的，用的矩陣快速冪求的斐波那切數(shù)列，套用公式，當(dāng)天寫完之后wa了，過(guò)了幾天后回來(lái)看，發(fā)現(xiàn)自己在矩陣快速冪的結(jié)構(gòu)體變量中設(shè)的是int而不是long long，模板用的也一直是int，覺(jué)得不會(huì)超，后來(lái)改成long long就A了，結(jié)果證明還是超了。推出來(lái)的公式是：

n=1：a

n=2：b

n=3：ab

n=4：ab²

n=5：a²b³

n=6：a³b⁵

n=7：a⁵b⁸

n=8：a⁸b¹³

正常人應(yīng)該都能看出規(guī)律了吧，就是斐波那切數(shù)列，由于指數(shù)比較大，要用到指數(shù)循環(huán)節(jié)的公式，中間用矩陣快速冪求斐波那切數(shù)列。具體代碼：

View Code 1 #include<iostream> 2 #include<cstdio> 3 #include<cmath> 4 #include<algorithm> 5 #include<cstring> 6 #include<cmath> 7 using namespace std; 8 __int64 euler(__int64 x){ 9 __int64 i, res = x; 10 for(i=2;i<(__int64)sqrt(x*10.0)+1;i++){ 11 if(x%i==0){ 12 res = res/i*(i-1); 13 while(x%i==0) x/=i; 14 } 15 } 16 if(x>1) res = res/x*(x-1); 17 return res; 18 } 19 __int64 quickpow(__int64 m, __int64 n, __int64 k){ 20 __int64 b = 1; 21 while(n>0){ 22 if(n&1){ 23 b = (b*m)%k; 24 } 25 n = (n>>1); 26 m = (m*m)%k; 27 } 28 return b; 29 } 30 typedef struct{ 31 __int64 m[2][2]; 32 }Matrix; 33 Matrix P = {0,1,1,1}, I = {1,0,0,1}; 34 Matrix matrixmul(Matrix a,Matrix b,__int64 p) //矩陣乘法 35 { 36 int i,j,k; 37 Matrix c; 38 for (i = 0 ; i < 2; i++) 39 for (j = 0; j < 2;j++) 40 { 41 c.m[i][j] = 0; 42 for (k = 0; k < 2; k++){ 43 c.m[i][j] += (a.m[i][k] * b.m[k][j])%p; // 取模的值 44 } 45 c.m[i][j] %= p; 46 } 47 return c; 48 } 49 50 Matrix matrix_exp(Matrix P, Matrix I, __int64 n,__int64 p) 51 { 52 Matrix m = P, b = I; 53 while (n >= 1) 54 { 55 if (n & 1) 56 b = matrixmul(b,m,p); 57 n = n >> 1; 58 m = matrixmul(m,m,p); 59 } 60 return b; 61 } 62 int main(){ 63 int i, j, k, l, t, T; 64 __int64 a, b, p, n; 65 __int64 f1, f2, f3, phip, aa, bb; 66 scanf("%d",&T); 67 for(t=1;t<=T;t++){ 68 scanf("%I64d%I64d%I64d%I64d",&a,&b,&p,&n); 69 phip = euler(p); 70 printf("Case #%d: ",t); 71 if(n==1){ 72 printf("%I64d\n",a%p);continue; 73 } 74 if(n==2){ 75 printf("%I64d\n",b%p);continue; 76 } 77 if(n==3){ 78 printf("%I64d\n",((a%p)*(b%p))%p);continue; 79 } 80 f1 = 0; f2 = 1; k = 0; 81 for(i=4;i<=n;i++){ 82 f3 = f1+f2; 83 if(f3>=phip){ 84 f3 %= phip; 85 k = 1;break; 86 } 87 f1 = f2; f2 = f3; 88 } 89 Matrix tmp; 90 if(k){ 91 tmp = matrix_exp(P,I,n-3,phip); 92 f1 = tmp.m[1][0]; f2 = tmp.m[1][1]; 93 aa = f2%phip+phip; 94 f3 = f1+f2; 95 bb = f3%phip+phip; 96 } 97 else{ 98 aa = f3; 99 f3 = f1+f2; 100 bb = f3; 101 } 102 printf("%I64d\n",(quickpow(a,aa,p)*quickpow(b,bb,p))%p); 103 } 104 return 0; 105 }

最近的一道題就是前幾天多校的題了，還是在那以后才會(huì)的這個(gè)公式，后來(lái)看了題解做的這題，那個(gè)trick也不是一般的坑人啊。

題意：給出三個(gè)數(shù)?(b, P and M)，其中 ( 0<=b<P, 1<=P<=10^5, 1 <= M <=2^64 – 1 )，M的范圍即暗示要用unsigned long long了，求滿足n^n!Ξb (mod p)，（0≤n≤M）的n有多少個(gè)。也是大整數(shù)冪，其中指數(shù)很大，所以要用到之前說(shuō)的指數(shù)循環(huán)節(jié)的公式

A^x = A^(x % Phi(C) + Phi(C)) (mod C)，其中x≥Phi(C)

對(duì)于n!的處理，主要分為一下3部分處理：

1，n很小的時(shí)候，直接枚舉就可以了，很小指的是n!<phip，此時(shí)上述公式也不適用；

2，公式適用要求x≥phip，此時(shí)n^n!Ξn^n!%phip+phipΞb (mod p)，這樣可以判斷n^n!Ξb (mod p)是否成立，但對(duì)于每一個(gè)n只是套用公式判斷是否同余，仍然需要逐個(gè)枚舉是否滿足，而M特別大，枚舉所有數(shù)必然超時(shí)；

3，可以進(jìn)一步發(fā)現(xiàn)當(dāng)某個(gè)n!%phip==0時(shí)，之后的所有n!都能整除phip，上述公式等價(jià)于n^n!Ξn^phipΞb (mod p)，指數(shù)為固定值，這樣就能看出循環(huán)節(jié)的公式了，根據(jù)乘法同余式(shit,這個(gè)也看了好久，phip個(gè)n相乘)n^phipΞ(n%p)^phipΞb (mod p)，所以在枚舉p個(gè)n就可以了，當(dāng)其中某個(gè)n成立時(shí)，可以知道其后≤M的所有模p同余的數(shù)的個(gè)數(shù)，答案就出來(lái)了。（大trick見代碼）

1 #include<iostream> 2 #include<cmath> 3 #include<cstdio> 4 #include<cstring> 5 #include<algorithm> 6 #define see(x) cout<<#x<<":"<<x<<endl; 7 using namespace std; 8 typedef unsigned __int64 LLU; 9 LLU euler(LLU x){ 10 LLU i, res = x; 11 for(i=2;i<(LLU)sqrt(x*10.0)+1;i++){ 12 if(x%i==0){ 13 res = res/i*(i-1); 14 while(x%i==0) x/=i; 15 } 16 } 17 if(x>1) res = res/x*(x-1); 18 return res; 19 } 20 21 LLU quickpow(LLU m, LLU n, LLU k){ 22 LLU b = 1; 23 while(n>0){ 24 if(n&1) 25 b = (b*m)%k; 26 n = n>>1; 27 m = (m*m)%k; 28 } 29 return b; 30 } 31 LLU f[100001]; 32 int main(){ 33 //freopen("1005.in","r",stdin); 34 //freopen("out.txt","w",stdout); 35 int t, T, i , k, l, flag; 36 LLU b, p, m, phip, ans; 37 scanf("%d",&T); 38 for(t=1;t<=T;t++){ 39 ans = 0; flag = 0; 40 //cin>>b>>p>>m; 41 scanf("%I64u%I64u%I64u",&b,&p,&m); 42 if(b==0&&p==1&&m==18446744073709551615ull){ 43 printf("Case #%d: 18446744073709551616\n",t);continue; 44 }//這里是個(gè)大trick，m==18446744073709551615就是2^64-1，如果b==0，p==1，即[0,m]里面所有的數(shù)模1都為0，所以一共有2^64個(gè)，而2^64已經(jīng)超過(guò)了unsigned long long，所以要特判輸出 45 phip = euler(p); 46 f[0] = 1; 47 if(b==0){ 48 ans++; 49 } 50 for(i=1;i<=m;i++){ 51 f[i] = f[i-1]*i; 52 if(f[i]>=phip){ 53 f[i] = f[i]%phip; 54 flag = 1; 55 if(f[i]==0){ 56 break; 57 } 58 } 59 if(flag){ 60 if(quickpow(i,f[i]+phip,p)==b){ 61 ans++; 62 63 } 64 } 65 else{ 66 if(quickpow(i,f[i],p)==b){ 67 ans++; 68 } 69 } 70 } 71 for(k=0;i<=m&&k<p;i++,k++){ 72 if(quickpow(i,phip,p)==b){ 73 ans = ans+1+(m-i)/p; 74 } 75 } 76 printf("Case #%d: %I64u\n",t,ans); 77 //cout<<ans<<endl; 78 } 79 return 0; 80 }

利用此題，親測(cè)杭電oj，可以定義long long，只是輸入輸出不能用%lld，可以用cin，cout，如果用scanf，printf就只能用%I64d，所以要定義__int64。同long long也可以定義unsigned __int64，輸入輸出可以用%I64u。

關(guān)于數(shù)論題目的總結(jié)：

1，數(shù)論題目，代碼不長(zhǎng)，一般知道相關(guān)知識(shí)，即可求解，但是也要注意細(xì)節(jié)，以免大意失荊州～～

2，數(shù)學(xué)題目以后直接所有變量都設(shè)成long long吧，（：在這上面摔過(guò)很多次了

?

?

轉(zhuǎn)載于:https://www.cnblogs.com/celia01/archive/2012/08/03/2621795.html

總結(jié)

以上是生活随笔為你收集整理的求 A^B mod C. (1=A,C=1000000000,1=B=10^1000000).（fzu1759，hdu3221，hdu4335）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。