首页 > 代码库 > 【poj2154】 Color
【poj2154】 Color
http://poj.org/problem?id=2154 (题目链接)
题意
n个珠子的项链，可以染上n中颜色，项链可以旋转不能翻转，求染色方案数。
Solution
经典的公式：
\begin{aligned} ans &= \sum_{i=0}^{n-1} gcd(n,i)\\ &= \sum_{d|n} (n^{d-1}*φ(\frac{n}{d})) \end{aligned}
于是就可以求了，然而时限卡太死，只能用int，还必须枚举质数求phi。。
代码
// poj2154#include<algorithm>#include<iostream>#include<cstdlib>#include<cstring>#include<cstdio>#include<cmath>#define LL long long#define inf 1<<30#define Pi acos(-1.0)#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);using namespace std;bool vis[1000010];int p[100010],P;int phi(int x) { int t=x; for (int i=1;p[i]<=sqrt(x);i++) if (x%p[i]==0) { t=t-t/p[i]; while (x%p[i]==0) x/=p[i]; } if (x>1) t=t-t/x; return t%P;}int power(int a,int b) { int res=1; while (b) { if (b&1) res=res*a%P; b>>=1;a=a*a%P; } return res;}int main() { for (int i=2;i<=1000000;i++) { if (!vis[i]) p[++p[0]]=i; for (int j=1;j<=p[0] && p[j]*i<=1000000;j++) { vis[p[j]*i]=1; if (i%p[j]==0) break; } } int n,ans; int T;scanf("%d",&T); while (T--) { scanf("%d%d",&n,&P);ans=0; for (int i=1;i*i<=n;i++) if (n%i==0) { ans+=power(n%P,i-1)*phi(n/i); if (i*i!=n) ans+=power(n%P,n/i-1)*phi(i); ans%=P; } printf("%d\n",ans); } return 0;}
【poj2154】 Color
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。