【题解】LOJ 2085 「NOI2016」循环之美

Problem

若 $\frac{x}{y}$ 在 $k$ 进制下为无限纯循环小数,则它为“美的”
求 $x\in[1,n],y\in[1,m]$ 在 $k$ 进制下有多少个本质不同的无限纯循环小数

Thought

可以发现, $\frac{x}{y}$ 在 $k$ 进制下为无限纯循环小数当且仅当 $gcd(y,k)=1$

那么答案为:

$$ \sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i,j)=1][gcd(j,k)=1] $$

经变形可得:

$$ \sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(j,k)=1]\sum_{d|gcd(i,j)}\mu(d)\\ \sum_{d=1}^{n}\mu(d)\sum_{i=1}^{\frac{n}{d}}\sum_{j=1}^{\frac{m}{d}}[gcd(dj,k)=1]\\ \sum_{d=1}^{n}[gcd(d,k)=1]\mu(d)\frac{n}{d}\sum_{j=1}^{\frac{m}{d}}[gcd(j,k)=1]\\ $$

令 $pre(n)=\sum_{i=1}^{n}[gcd(i,k)=1],(n\leq k)$

$$ \sum_{i=1}^{n}[gcd(i,k)=1]=(n/k)*pre[k]+pre[n \% k] $$

那么只需要考虑前面的 $\sum_{d=1}^{n}[gcd(d,k)=1]\mu(d)$ 如何计算前缀和

令 $S(n)=\sum_{i=1}^{n}\mu(i),F(n)=\sum_{i=1}^{n}[gcd(i,k)=1]\mu(i)$ 显然有

$$ F(n)=S(n)-\sum_{d=2,d|k}^{n}\sum_{i=1}^{n}[gcd(i,k)=d]*\mu(i)\\ =S(n)-\sum_{d=2,d|k}^{n}\sum_{i=1}^{\frac{n}{d}}[gcd(i,k)=1]*\mu(i)*\mu(d)\\ =S(n)-\sum_{d=2,d|k}^{n}\mu(d)\sum_{i=1}^{\frac{n}{d}}[gcd(i,k)=1]\mu(i)\\ =S(n)-\sum_{d=2,d|k}^{n}\mu(d)F(\frac{n}{d}) $$

杜教筛搞一搞完事

Code

#include <bits/stdc++.h>
using namespace std;
int read() {
    int ans = 0, flag = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}
const int N = 1000010;
const int Top = 1000000;

typedef long long LL;

int mu[N], s[N];
int f[N];

int sta[N], top;

bool nop[N];
int pri[N], priCnt;

int num[2010];
int n, m, k;

unordered_map <int, LL> S, F;

int gcd(int a, int b) {return b ? gcd(b, a % b) : a;}

void getPri() {
    f[1] = s[1] = mu[1] = 1;
    for(int i = 2; i <= Top; ++ i) {
        if(!nop[i]) {
            pri[++ priCnt] = i;
            mu[i] = - 1;
        }
        for(int j = 1; j <= priCnt && i * pri[j] <= Top; ++ j) {
            nop[i * pri[j]] = 1;
            if(i % pri[j])
                mu[i * pri[j]] = - mu[i];
            else {
                mu[i * pri[j]] = 0;
                break;
            }
        }
        s[i] = s[i - 1] + mu[i];
        f[i] = f[i - 1] + (gcd(i, k) == 1) * mu[i];
    }
}

LL calS(int n) {
    if(n <= Top)
        return s[n];
    if(S.count(n))
        return S[n];
    LL ans = 1, pos;
    for(int i = 2; i <= n; i = pos + 1) {
        pos = n / (n / i);
        ans -= calS(n / i) * (pos - i + 1);
    }
    S[n] = ans;
    return ans;
}

LL calF(int n) {
    if(n <= Top)
        return f[n];
    if(F.count(n))
        return F[n];
    LL ans = calS(n);
    for(int i = 1; i <= top; ++ i)
        ans -= calF(n / sta[i]) * mu[sta[i]];
    F[n] = ans;
    return ans;
}

LL calP(int x) {return (x / k) * num[k] + num[x % k];}

int main() {
    n = read(); m = read(); k = read();

    getPri();

    for(int i = 1; i <= k; ++ i)
        num[i] = num[i - 1] + (gcd(i, k) == 1);
    
    for(int i = 2; i <= k; ++ i)
        if(k % i == 0)
            sta[++ top] = i;
    
    LL nowf = 0, pos = 0, ans = 0, lastf = 0;
    for(int i = 1, j = 1; i <= min(n, m); i = j + 1) {
        j = min(n / (n / i), m / (m / i));
        nowf = calF(j);
        ans += (nowf - lastf) * (n / i) * calP(m / i);
        lastf = nowf;
    }
    printf("%lld\n", ans);
    return 0;
}
Comments

添加新评论