设 f(n) 为模 n 时的答案, 由 2k mod n=2k mod φ(n)+φ(n)mod n(并不会证), 且 k mod φ(n)=f(φ(n)), 直接就可以得到一个递推式子. 记搜一发即可.
- #include<iostream>
- #include<cstdio>
- #include<cmath>
- #include<cstdlib>
- #include<cstring>
- #include<algorithm>
- using namespace std;
- int read()
- {
- int x=0,f=1;char c=getchar();
- while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
- while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
- return x*f;
- }
- #define N 10000010
- int T,n,f[N],phi[N],prime[N>>3],cnt=0;
- bool flag[N];
- int ksm(int a,int k,int p)
- {
- int s=1;
- for (;k;k>>=1,a=1ll*a*a%p) if (k&1) s=1ll*s*a%p;
- return s;
- }
- int calc(int n)
- {
- if (~f[n]) return f[n];
- return f[n]=ksm(2,calc(phi[n])+phi[n],n);
- }
- int main()
- {
- #ifndef ONLINE_JUDGE
- freopen("bzoj3883.in","r",stdin);
- freopen("bzoj3883.out","w",stdout);
- const char LL[]="%I64d\n";
- #else
- const char LL[]="%lld\n";
- #endif
- flag[1]=1;phi[1]=1;
- for (int i=2;i<=N-10;i++)
- {
- if (!flag[i]) prime[++cnt]=i,phi[i]=i-1;
- for (int j=1;j<=cnt&&prime[j]*i<=N-10;j++)
- {
- flag[prime[j]*i]=1;
- if (i%prime[j]==0) {phi[prime[j]*i]=phi[i]*prime[j];break;}
- else phi[prime[j]*i]=phi[i]*(prime[j]-1);
- }
- }
- memset(f,255,sizeof(f));f[1]=f[2]=0;
- T=read();
- while (T--)
- {
- n=read();
- printf("%d\n",calc(n));
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2794703.html