LG P4980【模板】Pólya 定理
\(\text{Solution}\)
\[ans = \frac{1}{n}\sum_{i=1}^n n^{(i,n)} = \frac{1}{n}\sum_{d|n}n^d\varphi(\frac{n}{d}) \]\(T\) 组数据，然而暴力计算就可以过
可靠点就用哈希表存下（然而更慢
\(\text{Code}\)
#include
#define RE register
#define IN inline
using namespace std;
typedef long long LL;
const int P = 1e9 + 7;
int n, t, tot;
LL ans;
IN int gcd(int x, int y){return (!y ? x : gcd(y, x % y));}
IN LL fpow(LL x, int y){LL s = 1; for(; y; y >>= 1, x = x * x % P) if (y & 1) s = s * x % P; return s;}
IN int getphi(int x)
{
int res = x;
for(RE int i = 2; i * i <= x; i++)
if (x % i == 0)
{
res = res / i * (i - 1);
while (x % i == 0) x /= i;
}
if (x > 1) res = res / x * (x - 1);
return res;
}
int main()
{
scanf("%d", &t);
for(; t; --t)
{
scanf("%d", &n), ans = 0;
for(RE int i = 1; i * i <= n; i++)
if (n % i == 0)
{
ans = (ans + fpow(n, i) * getphi(n / i) % P) % P;
if (i * i != n) ans = (ans + fpow(n, n / i) * getphi(i) % P) % P;
}
printf("%lld\n", ans * fpow(n, P - 2) % P);
}
}