hdu 4704 费马小定理 - c++编程基础

费马小定理+快速幂

费马小定理可以用来求解a的高次幂mod质数的值。前提是a与质数互质。

#include   
#include   
#include   
using namespace std;  
const int maxn=1e6+9,mod=1e9+7;  
char a[maxn];  
int cal(int m)  
{  
    long long ret=2,ans=1;  
    while(m)  
    {  
        if(m&1) ans=(ans*ret)%mod;  
        m/=2;  
        ret=(ret*ret)%mod;  
    }  
    return ans;  
}  
  
int main()  
{  
//    freopen("in.txt","r",stdin);  
    while(scanf("%s",a+1)!=EOF)  
    {  
        int n=strlen(a+1);  
        long long ret=0;  
        for(int i=1;i<=n;i++)  
        {  
            ret=(ret*10)%(mod-1);  
            ret=(ret+a[i]-'0')%(mod-1);  
        }  
        int ans=cal((ret+mod-1)%mod);  
        cout<