POJ 2154 Color Ploya定理
题意：用n种颜色去涂长度为n的项链，问有多少种方法，最后取模。思路：很容易看出是一道Ploya定理的题目，但是由于n的规模太大（10亿），因此不能暴力，需要用欧拉函数优化一下。具体来说，就是循环求最大公约数的时候可以优化。这样的话，这道题就基本解决了，注意求幂的时候用快速幂。最后还有一个问题就是最后的取余运算，因为我们所求出来的并不是最后的答案，最后的答案还需要除以n，这就有了新的问题。我们所求出的sum是一直不断取余后的sum，因此不能用sum直接去除n。倘若需要取余的数P为素数的话，我们可以求n在P中的乘法逆元，将除法转变为乘法。但是这道题对P没有限制，也就是说P不一定是素数，因此易做图(n,P) 不一定等于1，即n的乘法逆元不一定存在。此时，我们可以这样，在算快速幂的时候，让指数减去1，相当于除以n，这样，这道题就可以解决了。
代码：
[cpp]
#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 1000000000
int 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;
}
作者：wmn_wmn
补充：软件开发 , C++ ,
