【费马小定理】HDU4704-Sum

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #define m 1000000007
 6 using namespace std;
 7 typedef long long ll;
 8 const int MAXN=1000000+5;
 9 ll n;
10 char str[MAXN];
11 
12 void init()
13 {
14     n=0;
15     int len=strlen(str);
16     for (int i=0;i<len;i++)
17         n=(n*10+str[i]-'0')%(m-1);
18     n--;
19 }
20 
21 ll pow()
22 {
23     ll temp=n,k=2,ret=1;
24     while (temp)
25     {
26         if (temp&1) ret=ret*k%m;
27         temp>>=1;
28         k=(k*k)%m;
29     }
30     return ret;
31 }
32 
33 int main()
34 {
35     while (~scanf("%s",str))
36     {
37         init();
38         cout<<pow()<<endl;
39     }
40     return 0;
41 }