poj2154-color-polyan次二面体+欧拉函数优化

N<=1e9,O(nlogn)的做法会超时。从枚举置换转变为枚举轮换长度，然后可以利用欧拉函数，把复杂度变为O(√n * logn)

/*--------------------------------------------------------------------------------------*/

#include <algorithm>
#include <iostream>
#include <cstring>
#include <ctype.h>
#include <cstdlib>
#include <cstdio>
#include <vector>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <set>
#include <map>

//debug function for a N*M array
#define debug_map(N,M,G) printf("\n");for(int i=0;i<(N);i++)\
{for(int j=0;j<(M);j++){\
printf("%d",G[i][j]);}printf("\n");}
//debug function for int,float,double,etc.
#define debug_var(X) cout<<#X"="<<X<<endl;
#define LL long long
const int INF = 0x3f3f3f3f;
const LL LLINF = 0x3f3f3f3f3f3f3f3f;
/*--------------------------------------------------------------------------------------*/
using namespace std;

int N,M,T;
int MOD = 1e9+7;

int Eular(int n)
{
    int ans = n;
    for(int i=2;i*i<=n;i++)
    {
        if(n%i == 0)
        {
            ans -= ans/i;
            while(n%i == 0) n/= i;
        }
    }
    if(n>1) ans -= ans/n;
    return ans;
}
int pow_mod(int x,int cnt)
{
    int base = x%MOD,res = 1;
    while(cnt)
    {
        if(cnt&1) {res *= base;res %= MOD;}
        base *= base;base %= MOD;
        cnt >>= 1;
    }
    return res;
}

int polya(int n,int m)
{
    int res = 0;
    int i;
    for(i=1;i*i<n;i++)
    {
        if(n%i == 0)
        {
            res += Eular(i)%MOD * pow_mod(m,n/i-1)%MOD;res %= MOD;
            res += Eular(n/i)%MOD * pow_mod(m,i-1)%MOD;res %= MOD;
        }
    }
    if(i*i == n) res += Eular(i)%MOD*pow_mod(m,i-1)%MOD;
    return res%MOD;
}

int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&N,&MOD);
        printf("%d\n",polya(N,N));
    }
}