題意：此題跟POJ 2409類似，只不過只考慮旋轉，不考慮翻轉；
但是需要用到快速冪和歐拉函數的優化求解。
/*
旋轉：順時針旋轉i格的置換中，循環的個數為gcd（i,n），
每個循環的長度為n/gcd（i,n）。
如果枚舉旋轉的格數i,復雜度顯然較高。有沒有好方法呢？
可以不枚舉i,反過來枚舉L.托福答案
由于L|N,枚舉了L,再計算有多少個i使得0<=i<=n-1并且L=gcd（i, n）。
即gcd（i,n）=n/L.
不妨設a=n/L=gcd（i, n），
不妨設i=a*t則當且僅當gcd（L,t）=1時
Gcd（i,n）=gcd（a*L,a*t）=a.
因為0<=i<n,所以0<=t<n/a=L.
所以滿足這個條件的t的個數為Euler（L）。
*/
[cpp] view plaincopyprint?
#include <cstdio>
#include <cstring>
using namespace std;
const int maxisp = 50000 + 10;
const int maxp = 8000 + 10;
int num,n,MOD;
int prime[maxp];
int isprime[maxisp];
inline void get_prime（）
{
num=0;
for（int i=2;i<=maxisp;i++）
if（！isprime[i]）
{
prime[num++]=i;
for（int j=1;j*i<=maxisp;j++）
isprime[i*j]=1;
}
}
inline int euler（int x）
{
int res=x;
for（int i=0;i<num&&prime[i]*prime[i]<=x;i++）
{
if（x%prime[i]==0）
{
res=res/prime[i]*（prime[i]-1）；
while（x%prime[i]==0）
x/=prime[i];
}
}
if（x>1） res=res/x*（x-1）；
return res;
}
//快速冪模版 此處的int可換成long long
//（A*B）%MOD
inline int mul（int a,int b,int mod）
{
int res=0;
a%=mod,b%=mod;
while（b）
{
if（b&1）
{
res+=a;
res%=mod;
}
a《=1;
if（a>=mod） a%=mod;
b》=1;
}
return res;
}
//（A^N）%MOD
inline int pow_mod（int a,int n,int mod）
{
int res=1;
a%=mod;
while（n）
{
if（n&1） res=mul（res,a,mod）；
a=mul（a,a,mod）；
n》=1;
}
return res;
}
int main（）
{
int T;
get_prime（）；
scanf（"%d",&T）；
while（T--）
{
scanf（"%d%d",&n,&MOD）；
int ans=0,i;
for（i=1;i*i<n;i++）
{
if（n%i==0）//有長度為L的循環，就會有長度為n/L的循環。
ans=（ans+euler（i）%MOD*pow_mod（n,n/i-1,MOD）+euler（n/i）%MOD*pow_mod（n,i-1,MOD））%MOD;
}
if（i*i==n）//枚舉循環長度l,找出相應的i的個數：gcd（i,n）=n/l.
ans=（ans+euler（i）*pow_mod（n,i-1,MOD））%MOD;
printf（"%d\n",ans）；
}
return 0;
}