題意：用n種顏色去塗長度為n的項鏈，問有多少種方法，最後取模。
思路：很容易看出是一道Ploya定理的題目，但是由於n的規模太大（10億），因此不能暴力，需要用歐拉函數優化一下。具體來說，就是循環求最大公約數的時候可以優化。這樣的話，這道題就基本解決了，注意求冪的時候用快速冪。最後還有一個問題就是最後的取余運算，因為我們所求出來的並不是最後的答案，最後的答案還需要除以n，這就有了新的問題。我們所求出的sum是一直不斷取余後的sum，因此不能用sum直接去除n。倘若需要取余的數P為素數的話，我們可以求n在P中的乘法逆元，將除法轉變為乘法。但是這道題對P沒有限制，也就是說P不一定是素數，因此gcd(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
