\(\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 <cstdio>

#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);

	}

}

巴特西

LG P4980【模板】Pólya 定理

\(\text{Solution}\)

\(\text{Code}\)

最新文章

热门文章