[洛谷P4980]【模板】Pólya 定理
前言
模板题。
题目
洛谷
讲解
直接由 Pólya 定理得到下面的式子，然后暴力求就过了。(懒得对齐了，将就看吧)
\[\sum_{i=1}^{n} n^{\gcd(i,n)}=n\times ans\\ \frac{1}{n}\sum_{i=1}^nn^{\gcd(i,n)}\\ =\frac{1}{n}\sum_{d}n^{d}\sum_{i=1}^{\frac{n}{d}}[\gcd(\frac{n}{d},i)=1]\\ =\frac{1}{n}\sum_{d}n^{d}\varphi(\frac{n}{d})\\ \]完全不能接受，凭什么暴力能过啊！！！而且线性筛预处理一点甚至还要慢一些，我不能理解。
代码
//12252024832524
#include
#define TT template
using namespace std;
typedef long long LL;
const int MAXN = 100005;
const int MOD = 1e9+7;
int n;
LL Read()
{
LL x = 0,f = 1;char c = getchar();
while(c > '9' || c < '0'){if(c == '-')f = -1;c = getchar();}
while(c >= '0' && c <= '9'){x = (x*10) + (c^48);c = getchar();}
return x * f;
}
TT void Put1(T x)
{
if(x > 9) Put1(x/10);
putchar(x%10^48);
}
TT void Put(T x,char c = -1)
{
if(x < 0) putchar('-'),x = -x;
Put1(x); if(c >= 0) putchar(c);
}
TT T Max(T x,T y){return x > y ? x : y;}
TT T Min(T x,T y){return x < y ? x : y;}
TT T Abs(T x){return x < 0 ? -x : x;}
int qpow(int x,int y)
{
int ret = 1;
while(y){if(y & 1) ret = 1ll * ret * x % MOD;x = 1ll * x * x % MOD;y >>= 1;}
return ret;
}
LL phi(int x)
{
int ret = x;
for(int i = 2;i*i <= x;++ i)
if(x % i == 0)
{
while(x % i == 0) x /= i;
ret = ret / i * (i-1);
}
if(x > 1) ret = ret / x * (x-1);
return ret;
}
int main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
for(int T = Read(); T ;-- T)
{
n = Read(); LL mi = 1,ans = 0;
for(int d = 1;d*d <= n;++ d)
{
mi = mi * n % MOD;
if(n % d == 0)
{
ans = (ans + mi * phi(n/d)) % MOD;
if(n/d != d) ans = (ans + qpow(n,n/d) * phi(d)) % MOD;
}
}
Put(ans * qpow(n,MOD-2) % MOD,'\n');
}
return 0;
}