polya

发表于 更新于 分类于 ， 阅读次数：

传送门

题目描述：

给你$n$种颜色，再给你一个正$n$边形的项链，问你有多少种本质不同的染色方案。

注意本题的本质不同，定义为：只需要不能通过旋转与别的染色方案相同。

输入格式：第一行一个正整数$t$，表示数据组数，之后每一行一个数，代表$n$

输出格式：对于每一组数据，输出一个数，代表答案对$1e9+7$取模的结果。

样例输入：

1
2
3
4
5
6
5
1
2
3
4
5

样例输出：

1
2
3
4
5
1
3
11
70
629

数据规模约定：$n\leq10^9,t\leq10^3$

在这里就不介绍Poyla定理的具体内容了，讲一讲应该如何优化。
我们不难求得答案是$ans=\sum\limits_{i=1}^nn^{gcd(i,n)}$

但是直接枚举复杂度是$O(tnlg^2n)$的，我们想办法优化。

我们可以发现对于$n$的每一个因子进行枚举可以发现，对于$n$的每一个因子$d$，我们有$n^d$种染色方案，又有$\varphi(\frac{n}{d})$个$gcd(i,n)=d$的情况。
所以对于每一个$d$，我们将答案加上$n^d\varphi(\frac{n}{d})$

所以我们枚举$n$的因子即可，这样的复杂度可以变为$O(t(n\sqrt{n})^\frac{1}{2}lgn)$的，但这还不够，我们要继续优化。

我们可以先筛出每个质因子，然后再求欧拉函数的过程中，直接枚举质数即可。这样的复杂度可以变为$O(t(n^\frac{1}{2}lgn)^\frac{1}{2}lgn)$，就可以过了。

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <vector>
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define Pause system("pause")
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
const int maxn = 4e4;
int prime[maxn + 10], tot;
bool vis[maxn + 10];
void getprime()
{
    for (int i = 2; i <= maxn; i++)
    {
        if (!vis[i])
        {
            prime[tot++] = i;
        }
        for (int j = 0; j < tot && i * prime[j] <= maxn; j++)
        {
            vis[i * prime[j]] = 1;
            if (i % prime[j] == 0)
                break;
        }
    }
}
ll qp(ll a, ll b, ll mod)
{
    a %= mod;
    ll ans = 1;
    while (b)
    {
        if (b & 1)
            ans = ans * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ans%mod;
}
ll getphi(ll t, ll mod)
{
    ll ans = t;
    for (int i = 0; 1ll * prime[i] * prime[i] <= 1ll * t; i++)
    {
        if (t % prime[i] == 0)
        {
            ans = ans * (prime[i] - 1) / prime[i];
            while (t % prime[i] == 0)
                t /= prime[i];
        }
    }
    if (t != 1)
    {
        ans = ans * (t - 1) / t;
    }
    return ans % mod;
}
int main()
{
    IOS;
    getprime();
    int t;
    cin >> t;
    while (t--)
    {
        ll n, ans = 0;
        cin >> n;
        for (int i = 1; i * i <= n; i++)
        {
            if (i * i == n)
                ans += qp(n, i - 1, mod) * getphi(i, mod) % mod, ans %= mod;
            else if (n % i == 0)
            {
                ans += qp(n, n / i - 1, mod) * getphi(i, mod) % mod;
                ans += qp(n, i - 1, mod) * getphi(n / i, mod) % mod;
                ans %= mod;
            }
        }
        cout <<(ans%mod+mod)%mod << endl;
    }
    return 0;
}