大家好，欢迎来到IT知识分享网。
昨天做了一个题，简化题意后就是求2的n次方对1e9+7的模，其中1<=n<=10100000。这个就算用快速幂加大数也会超时，查了之后才知道这类题是对费马小定理的考察。
费马小定理：假如p是质数，且gcd(a,p)=1（a，p互质），那么 a^(p-1)≡1（mod p）。
由题可知，1e9+7是个质数（许多结果很大的题都喜欢对1e9+7取模），2是整数，a与p互质显而易见，所以现在我们的目的就是想办法把2^n%(1e9+7)降幂为2^k%(1e9+7)，令p=1e9+7，已知a^(p-1) = 1（mod p），且n可能很大很大，就看n里包括多少个p-1，把这些都丢掉求剩下的就好（就是求n mod (p-1)，根据取模的性质，这个过程可以将n从第一个数展开过程中边取模完成，详见代码)。假设有x个p-1，则：2^n = 2^(x*(p-1)) * 2^k = 1^x * 2^k = 2^k(mod p)，所以直接求2^k就好，k = n%(p-1)。
由于N过于长，就用字符串存储，之后边转化为数边取余。还有就是处理过后的N也不小，求次幂时需要用快速幂。
1 #include<cstdio> 2 #include<string> 3 #include<iostream> 4 #include<algorithm> 5 using namespace std; 6 7 typedef long long LL; 8 string n; 9 const LL mod=1000000007; 10 11 LL QuickPower(LL a,LL b){ 12 LL ans=1; 13 while(b){ 14 if(b&1){ 15 ans=(ans*a)%mod; 16 } 17 b>>=1; 18 a=(a*a)%mod; 19 } 20 return ans; 21 } 22 23 int main(){ 24 cin>>n; 25 LL k=(LL)(n[0]-'0'),mod1=mod-1; 26 for(int i=1;i<n.length();i++) 27 k=(k*10+(LL)(n[i]-'0'))%mod1; 28 printf("%lld\n",QuickPower(2,k)); 29 return 0; 30 }
免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://yundeesoft.com/27932.html
