BZOJ3884 上帝与集合的正确用法（欧拉函数）

　　设f(n)为模n时的答案，由2^k mod n=2^{k 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
";
#else
    const char LL[]="%lld
";
#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
",calc(n));
    }
    return 0;
}

BZOJ3884 上帝与集合的正确用法（欧拉函数）

相关推荐