首页 > 代码库 > [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;
}
[BZOJ 3884][欧拉定理]上帝与集合的正确使用方法
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。