Luogu

LOJ

分析

可以发现,$k$ 进制分数 $\frac{x}{y}$ 是纯循环的当且仅当 $\gcd(y,k)=1$。证明可以点这里

另外为了避免算重,我们只统计最简分数。

那么我们要求的东西就是(设 $l=\min(n,m)$)

$$ \begin{aligned} &\sum_{x=1}^n\sum_{y=1}^m[\gcd(x,y)=1][\gcd(y,k)=1]\\ =&\sum_{x=1}^n\sum_{y=1}^m\sum_{d|x,d|y}\mu(d)[\gcd(y,k)=1]\\ =&\sum_{d=1}^l\mu(d)\left\lfloor\frac{n}{d}\right\rfloor\sum_{d|y}^m[\gcd(y,k)=1]\\ =&\sum_{d=1}^l\mu(d)\left\lfloor\frac{n}{d}\right\rfloor\sum_{y=1}^{m/d}[\gcd(dy,k)=1]\\ =&\sum_{d=1}^l[\gcd(d,k)=1]\mu(d)\left\lfloor\frac{n}{d}\right\rfloor\sum_{y=1}^{m/d}[\gcd(y,k)=1] \end{aligned} $$

可以数论分块,则我们需要计算两个前缀和

$$ \begin{aligned} f(n)&=\sum_{i=1}^n[\gcd(i,k)=1]\\ g(n,k)&=\sum_{i=1}^n[\gcd(i,k)=1]\mu(i) \end{aligned} $$

这里为什么是 $g(n,k)$ 而不是 $g(n)$ 呢?这里先埋一个伏笔,看到后面自然就知道了(

首先考虑计算 $f(n)$。可以发现如果 $\gcd(i,k)=1$ 则 $\gcd(i+k,k)=1$,如果 $\gcd(i,k)\neq 1$ 则 $\gcd(i+k,k)\neq 1$。所以有

$$ f(n)=\left\lfloor\frac{n}{k}\right\rfloor f(k)+f(n\bmod k) $$

因为 $k\leq 2000$,所以直接预处理出 $f(0\sim k)$ 的值即可。

再考虑算 $g(n,k)$,有

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

这样子直接枚举约数递归下去算即可;当 $k=1$ 时无法继续往下递归,但此时相当于要求 $\mu(i)$ 的前缀和,杜教筛即可。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
#define mp make_pair
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int K=2000+10,L=1000000+10;

int n,m,k;

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

int p[L],v[L],mu[L],smu[L],cnt;
map<pair<int,int>,ll> M;
void sieve(int n) {
    mu[1]=1;
    for (int i=2;i<=n;++i) {
        if (!v[i]) p[++cnt]=i,mu[i]=-1;
        for (int j=1;j<=cnt&&i*p[j]<=n;++j) {
            v[i*p[j]]=1;
            if (i%p[j]) mu[i*p[j]]=-mu[i];
            else break;
        }
    }
    for (int i=1;i<=n;++i) smu[i]=smu[i-1]+mu[i];
}
ll G(int n,int k) {
    if (!n) return 0;
    if (k==1&&n<L) return smu[n];
    if (M.count(mp(n,k))) return M[mp(n,k)];
    if (k==1) {
        ll res=1;
        for (int l=2,r;l<=n;l=r+1) {
            r=n/(n/l);
            res-=(r-l+1)*G(n/l,k);
        }
        return M[mp(n,k)]=res;
    } else {
        ll res=0;
        for (int d=1;d*d<=k;++d) {
            if (k%d) continue;
            if (mu[d]) res+=G(n/d,d);
            if (d*d!=k&&mu[k/d]) res+=G(n/(k/d),k/d);
        }
        return M[mp(n,k)]=res;
    }
}

int main() {
    sieve(L-1);
    n=read(),m=read(),k=read();
    for (int i=1;i<=k;++i) f[i]=f[i-1]+(__gcd(i,k)==1);
    ll ans=0;
    for (int l=1,r;l<=min(n,m);l=r+1) {
        r=min(n/(n/l),m/(m/l));
        ans+=(G(r,k)-G(l-1,k))*(n/l)*F(m/l);
    }
    printf("%lld\n",ans);
    return 0;
}
最后修改:2020 年 06 月 09 日 03 : 28 PM