<div class="post_brief"><p>
首先是burnside，对于旋转x下都要当作一个置换，所以总共有n个。然后第i个的不动点数量等于n<sup>gcd(n,i)</sup>，然后统计一下个数是phi(gcd(n,i))个。</p>

 

然后发现要用奇奇怪怪的东西来求phi。我用的方法是分解质因数然后DFS，跑得飞快。

 

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;


#define _l (long long int)


const int maxn = 50009;


int n, mod;
int tp, pn[maxn], phi[maxn];
bool pr[maxn];


void pre() {
memset(pr, 0, sizeof(pr));
tp = 0;
phi[1] = 1;
for (int i = 2; i < maxn; ++ i) {
if (!pr[i]) {
pn[tp ++] = i;
phi[i] = i - 1;
}
for (int j = 0; j < tp && i * pn[j] < maxn; ++ j) {
pr[i * pn[j]] = 1;
if (i % pn[j] == 0) {
phi[i * pn[j]] = phi[i] * pn[j];
break;
}
else
phi[i * pn[j]] = phi[i] * phi[pn[j]];
}
}
}


int modPow(int a, int x) {
int s(1);
for (a %= mod; x; x >>= 1, a = _l a * a % mod)
if (x & 1)
s = _l s * a % mod;
return s;
}


int fv[maxn], fc[maxn], tv, ans;


void dfs(int p, int pf, int pv) {
if (p == tv)
ans = (ans + _l modPow(n, pv - 1) * pf) % mod;
else {
dfs(p + 1, pf, pv);
pf *= fv[p] - 1;
pv /= fv[p];
dfs(p + 1, pf, pv);
for (int i = 2; i <= fc[p]; ++ i) {
pf *= fv[p];
pv /= fv[p];
dfs(p + 1, pf, pv);
}
}
}


int calc() {
int x(n);
tv = 0;
for (int i = 0; i < tp && x > 1; ++ i)
if (x % pn[i] == 0) {
fv[tv] = pn[i];
fc[tv] = 0;
while (x % pn[i] == 0) {
++ fc[tv];
x /= pn[i];
}
++ tv;
}
if (x > 1) {
fv[tv] = x;
fc[tv] = 1;
++ tv;
}
ans = 0;
dfs(0, 1, n);
return ans;
}


int main() {
//freopen(“in.txt”, “r”, stdin);
int t;
pre();
scanf("%d", &t);
while (t –) {
scanf("%d%d", &n, &mod);
if (mod == 1)
puts(“0”);
else
printf("%d\n", calc());
}
}