题意：此题跟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;
}