首页 > 代码库 > [BZOJ 3884][欧拉定理]上帝与集合的正确使用方法

[BZOJ 3884][欧拉定理]上帝与集合的正确使用方法

看看我们机房某畸形写的题解:http://blog.csdn.net/sinat_27410769/article/details/46754209

此题为popoQQQ神犇所出,在此orz

#include<cstdio>
#include<cstring>
#include<cmath>
#define maxl 10000001

long long ans;
long long f[maxl];
bool vis[maxl];

long long pow(long long a,long long b,long long p)
{
    long long ans=1,cnt=a;
    while(b>0)
    {
        if(b&1)
            ans=(ans*cnt)%p;
        cnt=(cnt*cnt)%p;
        b=b>>1;
    }
    return ans;
}

long long phi(long long x)
{
    long long t=x,l=sqrt(x);
    for(long long i=2;i<=l;i++)
    if(x%i==0)
    {
        t=t/i*(i-1);
        while(x%i==0)
            x/=i;
    }
    if(x>1)
        t=t/x*(x-1);
    return t;
}

long long F(long long x)
{
    if(vis[x])
        return f[x];
    long long p=phi(x);
    f[x]=pow(2,F(p)+p,x);
    vis[x]=true;
    return f[x];
}

void mainwork()
{
    long long p;
    scanf("%lld",&p);
    ans=F(p);
}

void print()
{
    printf("%lld\n",ans);
}

int main()
{
    long long t;
    scanf("%lld",&t);
    f[1]=0;vis[1]=true;
    while(t--)
    {
        mainwork();
        print();
    }
    return 0;
}
<script type="text/javascript"> $(function () { $(‘pre.prettyprint code‘).each(function () { var lines = $(this).text().split(‘\n‘).length; var $numbering = $(‘
    ‘).addClass(‘pre-numbering‘).hide(); $(this).addClass(‘has-numbering‘).parent().append($numbering); for (i = 1; i <= lines; i++) { $numbering.append($(‘
  • ‘).text(i)); }; $numbering.fadeIn(1700); }); }); </script>

[BZOJ 3884][欧拉定理]上帝与集合的正确使用方法