题解 P3307 【[SDOI2013]项链】

小粉兔

2018-12-24 09:10:38

题解

yyb的题解有一个地方是错的,比如最开始的式子,应该是S3+S2*3+S1*2

题意简述:

这题分为两个部分:

① 有一些珠子,每个珠子可以看成一个无序三元组。三元组要满足三个数都在1m之间,并且三个数互质,两个珠子不同当且仅当这个三元组不同。计算有多少种不同的珠子。

② 把这些珠子串成一个环,要满足相邻的珠子不同。两个环不同当且仅当旋转任意角度后仍然不同。计算有多少种不同的环。

题解:

分成两部分做。

第一部分:

考虑计算三元组的个数,转无序为有序,再去重。

答案=(三个都不同的有序三元组方案)/6+(两个相同,另一个不同的方案)/3+(三个都相同的方案)。

容斥一下得到答案=(三元组的方案+二元组的方案*3+一元组的方案*2)/6。

因为一元组只有(1)满足条件,所以答案是(2+三元组的方案+二元组的方案*3)/6。

考虑如何求出两种方案。

三元组的方案是\sum_{i=1}^m\sum_{j=1}^m\sum_{k=1}^m[\gcd(i,j,k)=1],二元组同理。

显然是莫反套路,三元组的答案是\sum_{d=1}^m\mu(d){\left\lfloor\frac{m}{d}\right\rfloor}^3,二元组同理。

数论分块求出答案即可,最后乘上6的逆元。这一步复杂度\Theta(m+T\sqrt{m})

第二部分:

知道了不同珠子的数量,要求出本质不同的环的个数。

Burnside引理套路。最终方案数等于每个置换的不动点个数的平均数,即\frac{1}{n}\sum_{i=1}^nf(i)f(i)表示旋转i格的不动点数量。

稍微化简一下:\frac{1}{n}\sum_{d|n}\varphi(\frac{n}{d})f(d)

考虑计算f(x),当xn的因数时,f(x)就等于不考虑旋转时的长度为x的环的数量。

假设不同珠子的数量为k,不加证明地给出一个式子:f(x)=(k-1)^x+(-1)^x(k-1)。这个式子可以递推得出。

那么根据这个式子和上面的式子计算即可。

要注意n太大了,要求出\varphi的值比较困难,考虑DFS它的每个质因数,按照\varphi是个积性函数以及公式,求得\varphi

要注意,最后除掉n的时候,n可能是模数的倍数导致没有逆元。可以发现n不会是模数平方的倍数,所以把模数平方后再做一遍,最后除掉模数这个因子即可。

#include <cstdio>

#define reg register
typedef unsigned long long ULL;
const ULL MOD = 1000000007ll;
const ULL Inv61 = 166666668ll;
const ULL Inv62 = 833333345000000041ll;
ULL Mod;
ULL Inv6;
const int MN = 10000001;

ULL TN[11];
int TA[11], MA;

bool ip[MN];
int p[MN], pc;
int mu[MN];
inline void SieveInit() {
    ip[0] = ip[1] = 1;
    mu[1] = 1;
    for (reg int i = 2; i <= MA; ++i) {
        if (!ip[i])
            p[++pc] = i,
            mu[i] = -1;
        for (reg int j = 1; j <= pc; ++j) {
            reg int k = p[j] * i;
            if (k > MA) break;
            ip[k] = 1;
            if (i % p[j]) mu[k] = -mu[i];
            else break;
        }
    }
    for (reg int i = 2; i <= MA; ++i)
        mu[i] += mu[i - 1];
}

int O;
inline ULL Mul(ULL x, ULL y) {
    if (!O) return x * y % Mod;
    return (x * y - (ULL)((long double) x / Mod * y) * Mod + Mod) % Mod;
}

ULL N; int A;
ULL M;
inline void SolveM() {
    M = 2;
    for (reg int i = 1, j, k; i <= A; i = j + 1) {
        k = A / i, j = A / k;
        M = (M + Mul(Mul(Mul(k, k), k + 3), (mu[j] - mu[i - 1] + Mod) % Mod)) % Mod;
    }
    M = Mul(M, Inv6);
}

ULL Pow[60];
inline void PowInit() {
    Pow[0] = M - 1;
    for (reg int i = 1; i < 60; ++i) Pow[i] = Mul(Pow[i - 1], Pow[i - 1]);
}
inline ULL qPow(ULL E) {
    ULL A = 1;
    for (reg int j = 0; E; E >>= 1, ++j)
        if (E & 1) A = Mul(A, Pow[j]);
    return A;
}
inline ULL Inv(ULL B) {
    ULL A = 1;
    for (reg ULL E = MOD - 2; E; E >>= 1, B = B * B % MOD)
        if (E & 1) A = A * B % MOD;
    return A;
}

ULL b[15]; int e[15], cnt;
ULL Ans;
inline ULL F(ULL x) {
    return (qPow(x) + (x & 1 ? Mod - M + 1 : M - 1)) % Mod;
}
void DFS(int st, ULL now, ULL phi) {
    if (st > cnt) {
        Ans = (Ans + Mul(phi % Mod, F(N / now))) % Mod;
        return;
    }
    DFS(st + 1, now, phi);
    for (reg int i = 1; i <= e[st]; ++i) {
        now *= b[st];
        phi *= i == 1 ? b[st] - 1 : b[st];
        DFS(st + 1, now, phi);
    }
}
inline ULL Solve() {
    ULL NN = N; cnt = 0;
    for (reg ULL i = 2; i * i <= NN; ++i) if (NN % i == 0) {
        b[++cnt] = i, e[cnt] = 0;
        while (NN % i == 0) NN /= i, ++e[cnt];
    } if (NN > 1) b[++cnt] = NN, e[cnt] = 1;
    Ans = 0; DFS(1, 1, 1);
    if (O) Ans = Ans / MOD * Inv(N / MOD) % MOD;
    else Ans = Ans * Inv(N % MOD) % MOD;
    return Ans;
}

int main() {
    int Tests;
    scanf("%d", &Tests);
    for (int i = 1; i <= Tests; ++i)
        scanf("%llu%d", TN + i, TA + i),
        MA = TA[i] > MA ? TA[i] : MA;
    SieveInit();
    for (int i = 1; i <= Tests; ++i) {
        N = TN[i], A = TA[i];
        O = N % MOD ? 0 : 1;
        if (O) Mod = MOD * MOD, Inv6 = Inv62;
        else Mod = MOD, Inv6 = Inv61;
        SolveM();
        PowInit();
        printf("%llu\n", Solve());
    }
    return 0;
}