HDU-4704 Sum 大数幂取模

　　题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4704
　　题意：求a^n%m的结果，其中n为大数。
　　S(1)+S(2)+...+S(N)等于2^(n-1)，第一次多校都出过吧。然后就是一个裸的大数幂了。。
　　关于大数的A^B mod C推荐看AC神的两篇文章<如何计算A^B mod C>,<计算a^(n!) mod c>...
　　当然，这个还以一个更简单的方法，由费马小定理：a^(p-1)=1(mod p)，那么a^n=1(mod p)可以转化为：2^(n%(1e9+7-1)) % 1e9+7...
  1 //STATUS:C++_AC_15MS_1360KB
  2 #include <functional>
  3 #include <algorithm>
  4 #include <iostream>
  5 //#include <ext/rope>
  6 #include <fstream>
  7 #include <sstream>
  8 #include <iomanip>
  9 #include <numeric>
 10 #include <cstring>
 11 #include <cassert>
 12 #include <cstdio>
 13 #include <string>
 14 #include <vector>
 15 #include <bitset>
 16 #include <queue>
 17 #include <stack>
 18 #include <cmath>
 19 #include <ctime>
 20 #include <list>
 21 #include <set>
 22 //#include <map>
 23 using namespace std;
 24 //#pragma comment(linker,"/STACK:102400000,102400000")
 25 //using namespace __gnu_cxx;
 26 //define
 27 #define pii pair<int,int>
 28 #define mem(a,b) memset(a,b,sizeof(a))
 29 #define lson l,mid,rt<<1
 30 #define rson mid+1,r,rt<<1|1
 31 #define PI acos(-1.0)
 32 //typedef
 33 typedef __int64 LL;
 34 typedef unsigned __int64 ULL;
 35 //const
 36 const int N=10000010;
 37 const int INF=0x3f3f3f3f;
 38 const int MOD=1000000007,STA=8000010;
 39 const LL LNF=1LL<<60;
 40 const double EPS=1e-8;
 41 const double OO=1e15;
 42 const int dx[4]={-1,0,1,0};
 43 const int dy[4]={0,1,0,-1};
 44 const int day[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
 45 //Daily Use ...
 46 inline int sign(double x){return (x>EPS)-(x<-EPS);}
 47 template<class T> T gcd(T a,T b){return b?gcd(b,a%b):a;}
 48 template<class T> T lcm(T a,T b){return a/gcd(a,b)*b;}
 49 template<class T> inline T lcm(T a,T b,T d){return a/d*b;}
 50 template<class T> inline T Min(T a,T b){return a<b?a:b;}
 51 template<class T> inline T Max(T a,T b){return a>b?a:b;}
 52 template<class T> inline T Min(T a,T b,T c){return min(min(a, b),c);}
 53 template<class T> inline T Max(T a,T b,T c){return max(max(a, b),c);}
 54 template<class T> inline T Min(T a,T b,T c,T d){return min(min(a, b),min(c,d));}
 55 template<class T> inline T Max(T a,T b,T c,T d){return max(max(a, b),max(c,d));}
 56 //End
 57 
 58 #define nnum 1000005
 59 #define nmax 31625
 60 int flag[nmax], prime[nmax];
 61 int plen;
 62 void mkprime() {
 63     int i, j;
 64     memset(flag, -1, sizeof(flag));
 65     for (i = 2, plen = 0; i < nmax; i++) {
 66         if (flag[i]) {
 67             prime[plen++] = i;
 68         }
 69         for (j = 0; (j < plen) && (i * prime[j] < nmax); j++) {
 70             flag[i * prime[j]] = 0;
 71             if (i % prime[j] == 0) {
 72                 break;
 73             }
 74         }
 75     }
 76 }
 77 int getPhi(int n) {
 78     int i, te, phi;
 79     te = (int) sqrt(n * 1.0);
 80     for (i = 0, phi = n; (i < plen) && (prime[i] <= te); i++) {
 81         if (n % prime[i] == 0) {
 82             phi = phi / prime[i] * (prime[i] - 1);
 83             while (n % prime[i] == 0) {
 84                 n /= prime[i];
 85             }
 86         }
 87     }
 88     if (n > 1) {
 89         phi = phi / n * (n - 1);
 90     }
 91     return phi;
 92 }
 93 int cmpCphi(int p, char *ch) {
 94     int i, len;
 95     LL res;
 96     len = strlen(ch);
 97     for (i = 0, res = 0; i < len; i++) {
 98         res = (res * 10 + (ch[i] - '0'));
 99         if (res > p) {
100             return 1;
101         }
102     }
103     return 0;
104 }
105 int getCP(int p, char *ch) {
106     int i, len;
107     LL res;
108     len = strlen(ch);
109     for (i = 0, res = 0; i < len; i++) {
110         res = (res * 10 + (ch[i] - '0')) % p;
111     }
112     return (int) res;
113 }
114 int modular_exp(int a, int b, int c) {
115     LL res, temp;
116     res = 1 % c, temp = a % c;
117     while (b) {
118         if (b & 1) {
119             res = res * temp % c;
120         }
121         temp = temp * temp % c;
122         b >>= 1;
123     }
124     return (int) res;
125 }
126 
127 int solve(int a, int c, char *ch) {
128     int phi, res, b;
129     phi = getPhi(c);
130     if (cmpCphi(phi, ch)) {
131         b = getCP(phi, ch) + phi;
132     } else {
133         b = atoi(ch);
134     }
135     res = modular_exp(a, b, c);
136     return res;
137 }
138 
139 void getch(char ch[])
140 {
141     int i,j,num,len=strlen(ch);
142     ch[len-1]--;
143     if(ch[len-1]>='0')return;
144     ch[len-1]='9';
145     for(i=len-2;i>=0;i--){
146         num=ch[i]-1;
147         if(num>='0'){
148             ch[i]=num;
149             if(i==0 && ch[i]=='0')break;
150             return;
151         }
152         ch[i]='9';
153     }
154     for(i=0;i<=len;i++){
155         ch[i]=ch[i+1];
156     }
157 }
158 
159 int main() {
160  //   freopen("in.txt", "r", stdin);
161     int a, c;
162     int ans;
163     char ch[nnum];
164     mkprime();
165     while (~scanf("%s",ch)) {
166         getch(ch);
167 
168         a=2,c=MOD;
169         ans=solve(a % c, c, ch);
170         printf("%d
",ans);
171     }
172     return 0;
173 }