NOI2016 循环之美题解

1. 题意

求在 K 进制下，表示为 \dfrac{x}{y}(x\leq N,y\leq M) 的不相等纯循环小数个数。

N,M\leq 10^9,K\leq 2000。

2. 模型转换

首先，K 进制下纯循环小数都可以表示成 \dfrac{x}{K^{\alpha}-1} 的形式。也就是说，分母 y 需要满足：存在 \alpha \in \mathbb{N}^*，使得 y\mid K^{\alpha}-1。这个条件可以等价地转化为 K 与 y 互质。

然后，题目要求不相等的纯循环小数个数。我们不妨用最简分数来代表一类相等的小数，即令 x 与 y 互质。

那么题目可以转化为求

Ans=\sum_{y=1}^M[\gcd(y,K)=1]\sum_{x=1}^N[\gcd(x,y)=1]

3. 公式推导

首先对内层和式莫比乌斯反演。

\begin{aligned} Ans=&\sum_{y=1}^{M}[\gcd(y,K)=1]\sum_{d\mid y}\mu(d)\left\lfloor\frac{N}{d}\right\rfloor\\ =&\sum_{d}\mu(d)\left\lfloor\frac{N}{d}\right\rfloor\sum_{i=1}^{M/d}[\gcd(id,K)=1]\\ =&\sum_{d}\mu(d)[\gcd(d,K)=1]\left\lfloor\frac{N}{d}\right\rfloor\sum_{i=1}^{M/d}[\gcd(i,K)=1] \end{aligned}

设 f(n)=\sum\limits_{i=1}^{n}[\gcd(i,K)=1]，g_k(n)=\mu(n)[\gcd(n,k)=1]，则

Ans=\sum_d g_K(d)\left\lfloor\frac{N}{d}\right\rfloor f\left(\left\lfloor\frac{M}{d}\right\rfloor\right)

带下取整的部分可以整除分块了，现在只需快速求出 f(n) 和 g_K(n) 的前缀和即可。

前者比较好求，有

f(n)=\sum_{i=1}^{n}[\gcd(i,K)=1]=\left\lfloor\frac{n}{K}\right\rfloor\varphi(K)+f(n\bmod K)

因为 K 很小，暴力预处理出 f(0),\cdots ,f(K) 即可在 O(\log n) 时间内求出任意一个 f(n)。

而对于后者，设 S_k(n)=\sum\limits_{i=1}^{n}g_K(i)，则有

\begin{aligned} S_k(n)=&\sum_{i=1}^{n}\mu(i)[\gcd(i,k)=1]\\ =&\sum_{i=1}^{n}\mu(i)\sum_{d\mid i\wedge d\mid k}\mu(d)\\ =&\sum_{d\mid k}\mu(d)\sum_{i=1}^{n/d}\mu(id)\\ =&\sum_{d\mid k}\mu(d)^2\sum_{i=1}^{n/d}\mu(i)[\gcd(i,d)=1]\\ =&\sum_{d\mid k}\mu(d)^2S\left(\left\lfloor\frac{n}{d}\right\rfloor,d\right) \end{aligned}

边界为 S_1(n)=\sum\limits_{i=1}^{n}\mu(i)，可以用杜教筛在 O(n^{2/3}) 的时间内求出。求解 g_k(n) 会有 O(d(k)\sqrt n) 个点值需要计算，其中 d(K) 为 K 的约数个数。因此总复杂度为 O(K\log K+N^{2/3}+d(K)\sqrt N)，这里视 N,M 同阶。

4. 代码

#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;
const int MAXK=2005;
const int MAXL=1000005;
struct Hash {
    static const int SIZE=5000000;
    static const int MOD=19260817;
    static const int BASE=6662333;
    static int hsh(int n, int k) {
        return (1ll*n*BASE+k)%MOD;
    }
    int cnt, x[SIZE], y[SIZE], v[SIZE];
    int head[MOD], nxt[SIZE];
    int& operator () (int n, int k) {
        int t=hsh(n, k), i=head[t];
        while (i&&(x[i]!=n||y[i]!=k)) i=nxt[i];
        if (!i) {
            i=++cnt, x[i]=n, y[i]=k;
            nxt[i]=head[t], head[t]=i;
        }
        return v[i];
    }
};
int N, M, K, L, cp;
vector<int> fac[MAXK];
int mu[MAXL], pri[MAXL];
bool mark[MAXL];
int f[MAXK], g1[MAXL];
Hash g;
int F(int n) {
    if (n<=K) return f[n];
    return n/K*f[K]+F(n%K);
}
int G1(int n) {
    if (n<=L) return g1[n];
    int &res=g(n, 1);
    if (res) return res;
    res=1;
    for (int i=2, j; i<=n; i=j+1) {
        j=n/(n/i);
        res-=(j-i+1)*G1(n/i);
    }
    return res;
}
int G(int n, int k) {
    if (n==0) return 0;
    if (k==1) return G1(n);
    int& res=g(n, k);
    if (res) return res;
    for (int d: fac[k])
        res+=mu[d]*mu[d]*G(n/d, d);
    return res;
}
int main() {
//  freopen("P1587.in", "r", stdin);
//  freopen("P1587.out", "w", stdout);
    scanf("%d%d%d", &N, &M, &K);
    for (int i=1; i<=K; i++) if (K%i==0)
        for (int j=i; j<=K; j+=i)
            fac[j].push_back(i);
    for (int i=1; i<=K; i++)
        f[i]=f[i-1]+(__gcd(i, K)==1);
    L=max((int)pow(min(N, M), 2.0/3), K);
    g1[1]=mu[1]=1;
    for (int i=2; i<=L; i++) {
        if (!mark[i]) pri[++cp]=i, mu[i]=-1;
        for (int j=1; j<=cp&&i*pri[j]<=L; j++) {
            mark[i*pri[j]]=1;
            if (i%pri[j]==0) { mu[i*pri[j]]=0; break; }
            mu[i*pri[j]]=-mu[i];
        }
        g1[i]=g1[i-1]+mu[i];
    }
    long long ans=0;
    for (int i=1, j; i<=N&&i<=M; i=j+1) {
        j=min(N/(N/i), M/(M/i));
        ans+=1ll*(G(j, K)-G(i-1, K))*(N/i)*F(M/i);
    }
    printf("%lld\n", ans);
    return 0;
}

冷滟泽的个人博客

NOI2016 循环之美题解