【NOI2016】循环之美

题目要求 \(\frac{x}{y}\) 是纯循环，如果记 \(\{x\}\) 为 \(x\) 的小数部分，那么就存在 \(l\) 满足：
\[ \{ \frac{x}{y} \} = \{ \frac{x k^l}{y} \} \]
这就要求 \(x \equiv xk^l (mod \; y)\)。又 \(gcd(x, y) = 1\)，我们得到 \(gcd(k, y) = 1\)

我们的答案就是
\[ \begin{split} Ans &= \sum_{x = 1} ^ n \sum_{y = 1} ^ m [gcd(x, y) = 1][gcd(y, k) = 1] \\ &= \sum_{y = 1} ^ m [gcd(y, k) = 1]\sum_{x = 1} ^ n \sum_{d|x\\d|y} \mu(d) \\ &= \sum_{d = 1} ^ n \mu(d) \lfloor \frac{n}{d} \rfloor \sum_{d|y} ^ m [gcd(y,k) = 1] \\ &= \sum_{d = 1} ^ n \mu(d) \lfloor \frac{n}{d} \rfloor \sum_{i = 1} ^ {\lfloor \frac{m}{d} \rfloor}[gcd(id,k) = 1] \\ &= \sum_{d = 1} ^ n \mu(d) \lfloor \frac{n}{d} \rfloor [gcd(d,k) = 1] \sum_{i = 1} ^ {\lfloor \frac{m}{d} \rfloor}[gcd(i,k) = 1] \end{split} \]
令 \(f(n) = \sum_{i = 1} ^ n [gcd(i, k) = 1]\)，则 $ f(n) = \lfloor \frac{n}{k} \rfloor \varphi(k) + f(n \mod k)$，可以预处理后 \(O(1)\) 计算。
\[ Ans = \sum_{d = 1} ^ n \lfloor \frac{n}{d} \rfloor f(\lfloor \frac{m}{d} \rfloor) \mu(d) [gcd(d,k) = 1] \]
对这个式子整除分块，现在就只需要计算 \(g(n) = \mu(n)[gcd(i,k) = n]\) 的前缀和，记为 \(h(n)\)。
\[ \begin{split} h(n) &= \sum_{i = 1} ^ {n} g(i) \\ &= \sum_{i = 1} ^ n \mu(i) - \sum_{d = 2, d | k} ^ n \sum_{i = 1} ^ n [gcd(i,k) = d] \mu(i) \\ &= \sum_{i = 1} ^ n \mu(i) - \sum_{d = 2, d | k} ^ n \sum_{i = 1} ^ {\lfloor \frac{n}{d} \rfloor} [gcd(i,\frac{k}{d}) = 1] \mu(id) \\ &= \sum_{i = 1} ^ n \mu(i) - \sum_{d = 2, d | k} ^ n \sum_{i = 1} ^ {\lfloor \frac{n}{d} \rfloor} \mu(i) \mu(d) [gcd(i,\frac{k}{d}) = 1] [gcd(i,d) = 1] \\ &= \sum_{i = 1} ^ n \mu(i) - \sum_{d = 2, d | k} ^ n \mu(d) \sum_{i = 1} ^ {\lfloor \frac{n}{d} \rfloor} \mu(i) [gcd(i,k) = 1] \\ &= \sum_{i = 1} ^ n \mu(i) - \sum_{d = 2, d | k} ^ n \mu(d) h(\lfloor \frac{n}{d} \rfloor) \end{split} \]
$ \sum_{i = 1} ^ n \mu(i)$ 可以用杜教筛算。

复杂度懒得分析了，随便调了个块大小过了。

#pragma GCC optimize("2,Ofast,inline")
#include<bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define LL long long
#define pii pair<int, int>
using namespace std;
const int Maxn = 1e6;
const int N = 1e6 + 10;
const int inf = 0x3f3f3f3f;

template <typename T> T read(T &x) {
    int f = 0;
    register char c = getchar();
    while (c > '9' || c < '0') f |= (c == '-'), c = getchar();
    for (x = 0; c >= '0' && c <= '9'; c = getchar())
        x = (x << 3) + (x << 1) + (c ^ 48);
    if (f) x = -x;
    return x;
}

LL n, m, k, tot;
int miu[N], ispri[N], pri[N], phi[N];
int f[N], smiu[N];
vector<int> divi;

struct Hashtable {
    static const int MOD = 1e7 + 7;
    int num[MOD], val[MOD];

    void ins(int x, int v) {
        int t = x % MOD;
        while (num[t] && num[t] != x) t = (t + 1 == MOD) ? 0 : t + 1;
        num[t] = x;
        val[t] = v;
    }

    int find(int x) {
        int t = x % MOD;
        while (num[t] && num[t] != x) t = (t == 0) ? MOD - 1 : t - 1;
        return val[t];
    }
} Map, h;

int gcd(int x, int y) {
    return (!y) ? x : gcd(y, x % y);
}

void prework() {
    miu[1] = 1;
    phi[1] = 1;
    for (int i = 2; i <= Maxn; ++i) {
        ispri[i] = 1;
    }
    for (int i = 2; i <= Maxn; ++i) {
        if (ispri[i]) {
            pri[++tot] = i;
            miu[i] = -1;
            phi[i] = i - 1;
        }
        for (int j = 1; j <= tot && i * pri[j] <= Maxn; ++j) {
            ispri[i * pri[j]] = 0;
            if (i % pri[j] != 0) {
                miu[i * pri[j]] = -miu[i];
                phi[i * pri[j]] = phi[i] * (pri[j] - 1);
            }
            else {
                miu[i * pri[j]] = 0;
                phi[i * pri[j]] = phi[i] * pri[j];
                break;
            }
        }
    }
    for (int i = 1; i <= k; ++i) {
        f[i] = f[i - 1] + (gcd(i, k) == 1);
    }
    for (int i = 1; i <= Maxn; ++i) {
        smiu[i] = smiu[i - 1] + miu[i];
    }
    for (int i = 1; i <= k; ++i) {
        if (k % i == 0) divi.pb(i);
    }
    memset(h.val, 0x3f, sizeof h.val);
}

inline int F(int n) {
    return n / k * phi[k] + f[n % k];
}

inline int nex(int n, int i) {
    return n / (n / i);
}

int calc_miu(int x) {
    if (x <= Maxn) return smiu[x];
    int ans;
    if (ans = Map.find(x)) return ans;
    ans = 1;
    for (int i = 2; i <= x; ++i) {
        int j = nex(x, i);
        ans -= (j - i + 1) * calc_miu(x / i);
        i = j;
    }
    Map.ins(x, ans);
    return ans;
}

int calc_h(LL x) {
    int S;
    if ((S = h.find(x)) != inf) return S;
    S = calc_miu(x);
    for (int i = 1; i < divi.size(); ++i) {
        if (divi[i] > x) break;
        S -= miu[divi[i]] * calc_h(x / divi[i]);
    }
    h.ins(x, S);
    return S;
}

int main() {
    read(n); read(m); read(k);
    prework();
    LL ans = 0;
    for (int i = 1; i <= n && i <= m; ++i) {
        int j = min(nex(n, i), nex(m, i));
        LL tmp = 1LL * (n / i) * F(m / i);
        LL sumg = calc_h(j) - calc_h(i - 1);
        ans += tmp * sumg;
        i = j;
    }
    cout << ans << endl;
    return 0;
}

【NOI2016】循环之美

原文：https://www.cnblogs.com/Vexoben/p/11831431.html