求2的n次方对1e9+7的模,n大约为10的100000次方(费马小定理)

  昨天做了一个题,简化题意后就是求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 }

 

上一篇:bzoj 4589 FWT


下一篇:hdu1181 dfs 字符串首尾可拼接,问是否可寻找到一条字串路径使得首尾分别是‘b’和‘m’,简单的搜索+回溯