M_sea

洛谷1587 [NOI2016]循环之美
Luogu分析首先有一个结论:如果 $k$ 进制下一个分数是纯循环小数,那么分母与 $k$ 互质。那么就是要求 $...
扫描右侧二维码阅读全文
04
2019/04

洛谷1587 [NOI2016]循环之美

Luogu

分析

首先有一个结论:如果 $k$ 进制下一个分数是纯循环小数,那么分母与 $k$ 互质。

那么就是要求 $\large\sum\limits_{i=1}^n\sum\limits_{j=1}^m[i\perp j][j\perp k]$ 。

也就是 $\large\sum\limits_{j=1}^m[\gcd(j,k)=1]\sum\limits_{i=1}^n[\gcd(i,j)=1]$ 。

根据 $\mu$ 的定义可以变为 $\large\sum\limits_{j=1}^m[\gcd(j,k)=1]\sum\limits_{i=1}^n\sum\limits_{d|i,d|j}\mu(d)$ 。

把 $d$ 提出来变为 $\large\sum\limits_{d=1}^n\mu(d)\sum\limits_{d|i}^n\sum\limits_{d|j}^m[\gcd(j,k)=1]$ 。

进一步变为 $\large\sum\limits_{d=1}^n[d\perp k]\mu(d)\sum\limits_{i=1}^{n/d}\sum\limits_{j=1}^{m/d}[gcd(j,k)=1]$ 。

也就是 $\large\sum\limits_{d=1}^n[d\perp k]\mu(d)\lfloor\frac{n}{d}\rfloor\sum\limits_{j=1}^{m/d}[gcd(j,k)=1]$ 。

于是现在要求两个前缀和: $\large f(x)=\sum\limits_{i=1}^x[gcd(i,k)=1]$ 和 $\large S(x)=\sum\limits_{i=1}^x[i\perp k]\mu(i)$ 。

感觉 $f$ 比较简单,先算 $f$ 。容易得到 $\large f(x)=\lfloor\frac{x}{k}\rfloor f(k)+f(x\%k)$ 。

然后来考虑 $S$ 怎么算。为了方便,我们加一维变成 $S(x,k)$ 。

那么就有 $\large S(x,k)=\sum\limits_{i=1}^x\mu(i)[\gcd(i,k)=1]$ 。

枚举 $\gcd$ ,变为 $\large\sum\limits_{i=1}^x\mu(i)\sum\limits_{d|i,d|k}\mu(d)$。

进几步变成 $\large\sum\limits_{d|k}\mu(d)\sum\limits_{i=1}^{x/d}\mu(id)$ 。

发现只有 $i\perp d$ 时有贡献,于是可以变成 $\large\sum\limits_{d|k}\mu(d)\sum\limits_{i=1}^{x/d}[i\perp d]\mu(i)\mu(d)$ 。

进一步变成 $\large\sum\limits_{d|k}\mu(d)^2\sum\limits_{i=1}^{x/d}[i\perp d]\mu(i)$ 。

后面的可以递归求,也就是说 $\large S(x,k)=\sum\limits_{d|k}\mu(d)^2S(\lfloor\frac{x}{d}\rfloor,d)$ 。

考虑边界是什么。当 $x=0$ 时,值为 $0$ ;当 $k=1$ 时,相当于求 $\mu$ 的前缀和,直接杜教筛即可。

然后就做完这题啦。具体实现及细节见代码。

代码

// =================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// =================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <map>
#define re register
#define mp make_pair
#define int long long
using namespace std;

inline 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 N=8000000+10;

int n,m,k;
int p[N],v[N],cnt=0;
int mu[N],smu[N],sco[N];
map<pair<int,int>,int> M;

inline void sieve(int n) {
    v[1]=mu[1]=1;
    for (re int i=2;i<=n;++i) {
        if (!v[i]) p[++cnt]=i,mu[i]=-1;
        for (re 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 (re int i=1;i<=n;++i) smu[i]=smu[i-1]+mu[i];
}

inline int sumf(int x) { return (x/k)*sco[k]+sco[x%k]; }

inline int sum(int x,int k) {
    if (!x) return 0;
    if (k==1&&x<=8e6) return smu[x];
    if (M.find(mp(x,k))!=M.end()) return M[mp(x,k)];
    if (k==1) {
        int ans=1;
        for (re int i=2,j;i<=x;i=j+1) {
            j=x/(x/i);
            ans-=(j-i+1)*sum(x/i,k);
        }
        return M[mp(x,k)]=ans;
    } else {
        int ans=0;
        for (re int i=1;i*i<=k;++i) {
            if (k%i) continue;
            if (mu[i]) ans+=sum(x/i,i);
            if (i*i!=k&&mu[k/i]) ans+=sum(x/(k/i),k/i);
        }
        return M[mp(x,k)]=ans;
    }
}

signed main() {
    sieve(8e6); n=read(),m=read(),k=read();
    for (re int i=1;i<=k;++i) sco[i]=sco[i-1]+(__gcd(i,k)==1);
    int ans=0;
    for (re int i=1,j,t=min(n,m);i<=t;i=j+1) {
        j=min(n/(n/i),m/(m/i));
        ans+=1ll*(sum(j,k)-sum(i-1,k))*(n/i)*sumf(m/i);
    }
    printf("%lld\n",ans);
    return 0;
}
最后修改:2019 年 04 月 04 日 05 : 25 PM

发表评论