首页 > 代码库 > POJ 2154 Color ——Burnside引理
POJ 2154 Color ——Burnside引理
【题目分析】
数据范围有些大。
然后遍求欧拉函数,遍求和就好了,注意取模。
【代码】
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; #define F(i,j,k) for (int i=j;i<=k;++i) #define D(i,j,k) for (int i=j;i>=k;--i) #define maxn 100005 #define inf 0x3f3f3f3f int n,p,x,sum; int ispr[maxn],pr[maxn],top=0; void init() { F(i,2,maxn-1) if (!ispr[i]) { pr[++top]=i; F(j,2,inf) { if (j*i>=maxn) break; ispr[j*i]=1; } } } int qpow(int a,int b) { a%=p; int ret=1; while (b) { if (b&1) (ret*=a)%=p; (a*=a)%=p; b>>=1; } return ret; } int phi(int n) { int ret=n; for (int i=1;pr[i]*pr[i]<=n&&i<=top;++i) if (n%pr[i]==0) { ret=ret-ret/pr[i]; while (n%pr[i]==0) n/=pr[i]; } if (n>1) ret=ret-ret/n; return ret%p; } int main() { init(); // F(i,1,top) printf("%d ",pr[i]); printf("\n"); scanf("%d",&x); while (x--) { sum=0; scanf("%d%d",&n,&p); for (int i=1;i*i<=n;++i) { if (n%i==0) { sum=(sum+(qpow(n,i-1)*phi(n/i))%p)%p; if (i*i!=n) sum=(sum+(qpow(n,n/i-1)*phi(i))%p)%p; } } printf("%d\n",sum); } }
POJ 2154 Color ——Burnside引理
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。