BZOJ-3884: 上帝与集合的正确用法

Description

多组询问，T<=1000 p<=10^7

设函数f(x)表示有x个2，该形式下的值。

将p按奇偶讨论：
偶数：将模数除以2^k (p=2^k*q) q为奇数
=只需计算原式mod q的值即可
奇数：欧拉定理
=只需计算原式mod 的值即可
直到计算的模数为1时返回0即可。
时间复杂度O(log n)

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
int n,pri[701000],phi[10001000],cnt;
void initialize()
{
    phi[1]=1;
    for(int i=2;i<=10000000;++i)
    {
        if(!phi[i]) phi[i]=i-1,pri[++cnt]=i;
        for(int j=1;i*pri[j]<=10000000&&j<=cnt;++j)
        {
            if(i%pri[j]) phi[i*pri[j]]=phi[i]*pri[j]-phi[i];
            else {phi[i*pri[j]]=phi[i]*pri[j]; break;}
        }
    }
}
int bin(int y,int mod)
{
    ll re=1,x=2;
    while(y)
    {
        if(y&1) re=re*x%mod;
        x=x*x%mod; y>>=1;
    }
    return re;
}
int ans(int mod)
{
    if(mod==1) return 0;
    int i=mod,j=0;
    for(i=mod;~i&1;++j,i>>=1);
    return mod/i*bin((ans(phi[i])-j)%phi[i]+phi[i],i);
}
int main()
{
    initialize(); int T; scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        printf("%d\n",ans(n));
    }
    return 0;
}