大数运算

 1 #include<bits/stdc++.h>
 2 char s[1000005];
 3 char st[1000005];
 4 long long qpow(long long a,long long b,long long mod)
 5 {
 6     long long  ans=1,temp=a;
 7     while(b)
 8     {
 9         if(b&1)
10         {
11             ans=(ans*temp)%mod;
12         }
13         b>>=1;
14         temp=temp*temp%mod;
15     }
16     return ans;
17 }
18 const int MAXN=1e5;
19 int  vis[MAXN],prime[MAXN];
20 int main()
21 {
22     long long i,j,n,euler,c,a,top;
23     top=0;
24     for (i=2; i<MAXN; i++)
25     {
26         if (!vis[i])
27         {
28             prime[top++]=i;
29         }
30         for(j=0; prime[j]*i<MAXN; j++)
31         {
32             vis[prime[j]*i]=1;
33             if(i%prime[j]==0)
34                 break;
35         }
36     }
37     while(scanf("%s",&s)!=EOF)
38     {
39         a = 2;///底数
40         n = 998244353;
41         euler=n;
42         c=n;
43         for(i=0; (long long)prime[i]*prime[i]<=n; i++)
44         {
45             if(n%prime[i]==0)
46             {
47                 euler=euler*(prime[i]-1)/prime[i];
48                 while(n%prime[i]==0)
49                 {
50                     n/=prime[i];
51                 }
52             }
53         }
54         if(n!=1)
55         {
56             euler=euler/n*(n-1);
57         }
58         long long b=0;
59         for(i=0; s[i]; i++)
60         {
61             b=(b*10+s[i]-‘0‘)%euler;
62         }
63         printf("%d\n",qpow(a,b+euler,c));
64     }
65     return 0;
66 }