POJ 2154 Color Ploya定理

来源：http://poj.org/problem?id=2154

题意：用n种颜色去涂长度为n的项链，问有多少种方法，最后取模。

思路：很容易看出是一道Ploya定理的题目，但是由于n的规模太大（10亿），因此不能暴力，需要用欧拉函数优化一下。具体来说，就是循环求最大公约数的时候可以优化，具体见http://blog.csdn.net/wmn_wmn/article/details/7733874。这样的话，这道题就基本解决了，注意求幂的时候用快速幂。最后还有一个问题就是最后的取余运算，因为我们所求出来的并不是最后的答案，最后的答案还需要除以n，这就有了新的问题。我们所求出的sum是一直不断取余后的sum，因此不能用sum直接去除n。倘若需要取余的数P为素数的话，我们可以求n在P中的乘法逆元，将除法转变为乘法。但是这道题对P没有限制，也就是说P不一定是素数，因此gcd(n,P) 不一定等于1，即n的乘法逆元不一定存在。此时，我们可以这样，在算快速幂的时候，让指数减去1，相当于除以n，这样，这道题就可以解决了。

代码：

#include <iostream>#include <cstdio>#include <string.h>#include <cmath>using namespace std;typedef long long ll;#define CLR(arr,val) memset(arr,val,sizeof(arr))const int N = 40000;#define M 1000000000int cnt,prime[N],cntprime,flag[N];int Mod;void init(){cntprime = 0;CLR(flag,0,sizeof(flag));for(int i = 2;i <= sqrt(M*1.0);++i){if(!flag[i]){  prime[cntprime++] = i;  for(int j = 2;j * i <= sqrt(M * 1.0);++j){    flag[j * i] = true;  }}}}int eular(int x){if(x == 1 || x == 2) return 1;int m = (int)sqrt(x + 0.5);int ans = x,y = x;for(int i = 0;prime[i] <= y && i <cntprime;++i){if(x % prime[i] == 0){  ans = ans/prime[i] * (prime[i]-1);  while(x%prime[i] == 0)  x /= prime[i];}if(x == 1)break;}if(x > 1)ans = ans/x * (x-1);return ans;}int binary_power(int n,int x){if(x == 0)return 1%Mod;if(x == 1)return n%Mod;int ans = binary_power(n,x/2);return ((ans*ans)%Mod * (x % 2 ? n:1)%Mod) % Mod;}int main(){init();int numcase;scanf("%d",&numcase);while(numcase--){  int n;  scanf("%d%d",&n,&Mod);  cnt = 0;  int sum = 0;  for(int i = 1;i <= sqrt(n*1.0);++i){  if(n % i == 0){  int y = n/i;  int z = eular(y);  int ans = binary_power(n%Mod,i-1);  ans = ((ans%Mod) * (z%Mod)) % Mod;  sum += ans;  sum %= Mod;  if(n/i != i){    z = eular(i);ans = binary_power(n%Mod,n/i-1);ans = ((ans%Mod) * (z%Mod)) % Mod;sum += ans;sum %= Mod;  }  }  }  printf("%d\n",sum);}return 0;}