【POJ 2154】Color

Solution

怎么说，这里是记录一个玄学优化吧。

先列出 (Polya) 定理吧：

[ans=frac{1}{|G|}sum_{k=1}^{g}m^{c(sigma_k)} ]

这道题只有旋转，于是我们的 (|G|==g) 就是 n 啦，而表示颜色种数的 m 也是 n 啦。

但是康康 n 的范围：(1e9) 艹！

于是我们调转枪头，我们发现循环节的长度相同时，此时的 i 不一定相同，这就是我们优化的突破口。

设 L 为循环节长度，易得 (L=frac{n}{gcd(i,n)})，其中 (gcd(i,n)) 是循环节的个数。

再设 (cnt=gcd(i,n)=frac{n}{L})。

因为 (cnt|i)，所以可令 (i=t*cnt)。（因为 (1<=i<=n)，所以 (1<=t<=frac{n}{cnt}=L)）

所以有：(gcd(i,n)==gcd(t*cnt,L*cnt)==cnt)。

上面这个式子就是使循环节长度为 L 的条件。

易得当 (gcd(t,L)==1) 时满足条件。

L 是可以以 (O(sqrt n)) 的复杂度枚举的，求出此时合法的 t 的个数就转换成了求 (phi(L))。

然后直接套上去就行了。

注意的是我们这里用两种求 (phi) 的方法为了降低点运行时间。直接算 (phi) 的那个方法可以证明我们之前筛的素数是够用的，因为我们先前筛的素数是 (1e6) 范围内，而 n 的范围是 (1e9) 之内，可以保证超过我们预处理范围的素数至多只有一种。

Code

上马！（/xyx

#include <cstdio>

const int N = 1e6;

int n, mod, cnt, phi[N + 5], p[N + 5];
bool vis[N + 5];

int read() {
    int x = 0, f = 1; char s;
    while((s = getchar()) < '0' || s > '9') if(s == '-') f = -1;
    while(s >= '0' && s <= '9') {x = (x << 1) + (x << 3) + (s ^ 48); s = getchar();}
    return x * f;
}

int Phi(int n) {
    if(n <= N) return phi[n] % mod;
    int ans = n;
    for(int i = 1; i <= cnt && p[i] * p[i] <= n; ++ i) {
        if(n % p[i] == 0) {
            ans -= ans / p[i];
            while(n % p[i] == 0) n /= p[i];
        }
    }
    if(n > 1) ans -= ans / n;
    return ans % mod;
}

void Euler() {
    phi[1] = 1;
    for(int i = 2; i <= N; ++ i) {
        if(! vis[i]) p[++ cnt] = i, phi[i] = i - 1;
        for(int j = 1; j <= cnt && p[j] * i <= N; ++ j) {
            vis[p[j] * i] = 1;
            if(i % p[j] == 0) {
                phi[p[j] * i] = phi[i] * p[j];
                break;
            }
            else phi[p[j] * i] = phi[i] * (p[j] - 1);
        }
    }
}

int qkpow(int x, int y) {
    int res = 1; x %= mod;
    while(y) {
        if(y & 1) (res *= x) %= mod;
        (x *= x) %= mod, y >>= 1;
    }
    return res;
}

int Polya() {
    int ans = 0;
    for(int i = 1; i * i <= n; ++ i) {
        if(n % i) continue;
        (ans += Phi(i) * qkpow(n, n / i - 1)) %= mod;
        if(i * i == n) break;
        (ans += Phi(n / i) * qkpow(n, i - 1)) %= mod;//减一是为了消去 Polya 式子前的那个分数
    }
    return ans;
}

int main() {
    Euler();
    for(int T = read(); T; -- T) {
        n = read(), mod = read();
        printf("%d
", Polya());
    }
    return 0;
}