洛谷P4980 【模板】Pólya 定理

解题思路

本题应用Pólya定理解决旋转群下的染色计数问题。对于正n边形的旋转群，群元素为旋转0°, ( 360°/n ), ( 2*360°/n ), ..., ( (n-1)*360°/n )，共n个元素。每个旋转元素的循环指数由其阶数决定，对于阶数为d的旋转，其循环分解中循环的个数为n/d。根据Pólya定理，不同染色方案数等于群中所有元素循环指数的平均值，即 ( \frac{1}{n} \sum_{d|n} \phi(d) m^{n/d} )，其中φ(d)为欧拉函数，d为n的所有正因子。

代码实现

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int MOD = 1e9 + 7;

ll euler(ll x) {
    ll res = x;
    for (ll i = 2; i * i <= x; ++i) {
        if (x % i == 0) {
            res = res / i * (i - 1);
            while (x % i == 0) x /= i;
        }
    }
    if (x > a) res = res / x * (x - 1);
    return res;
}

vector<ll> get_divisors(ll n) {
    vector<ll> divisors;
    for (ll i = 1; i * i <= n; ++i) {
        if (n % i == 0) {
            divisors.push_back(i);

【题解】洛谷P4980 【模板】Pólya 定理[Pólya+莫反]-CSDN博客