题解 P1587 【[NOI2016]循环之美】

· · 题解

upd：一个更简单的做法。

相等的纯循环小数只算一次，即对于一个分数 \frac{x}{y} 只在 x\perp y 时统计。

如果一个 k 进制最简分数 \frac{x}{y} 是纯循环小数，设其循环节长度为 l，必然有

\left\{\frac{xk^l}{y}\right\}=\left\{\frac{x}{y}\right\}

其中 \{x\} 表示取 x 的小数部分。即

\begin{aligned}\frac{xk^l}{y}-\left\lfloor\frac{xk^l}{y}\right\rfloor&=\frac{x}{y}-\left\lfloor\frac{x}{y}\right\rfloor \\ xk^l-y\left\lfloor\frac{xk^l}{y}\right\rfloor&=x-y\left\lfloor\frac{x}{y}\right\rfloor \\ xk^l&\equiv x\pmod y \\ k^l &\equiv 1\pmod y \end{aligned}

这推出 k\perp y。

于是答案为

\sum_{i=1}^n\sum_{j=1}^m [i\perp j][k\perp j]

接下来是传统艺能

\begin{aligned}\sum_{i=1}^n\sum_{j=1}^m [i\perp j][k\perp j]&=\sum_{i=1}^n\sum_{j=1}^m\sum_{d|i,d|j}\mu(d)[k\perp j] \\ &=\sum_{d=1}^{\min(n,m)} \mu(d)\sum_{i=1}^{\lfloor n/d \rfloor}\sum_{j=1}^{\lfloor m/d \rfloor}[jd\perp k] \\ &=\sum_{d=1}^{\min(n,m)} \mu(d)\left\lfloor \frac{n}{d}\right\rfloor\sum_{j=1}^{\lfloor m/d \rfloor}[j\perp k][d\perp k] \\ &=\sum_{d=1}^{\min(n,m)} \mu(d)[d\perp k]\left\lfloor \frac{n}{d}\right\rfloor\sum_{j=1}^{\lfloor m/d \rfloor}[j\perp k]\end{aligned}

考虑后面的那个和式怎么求，不妨设 g(n)=\sum\limits_{i=1}^n[i\perp k]，容易发现当 i>k 时根据 \gcd(i,k)=\gcd(i+k,k)，答案呈现一个长为 k 的循环，换句话说，就是

g(n)=\left\lfloor\frac{n}{k}\right\rfloor\varphi(k)+g(n\bmod k)

这一部分可以做到 O(k)-O(1)。

代回原式

\sum_{d=1}^{\min(n,m)} \left\lfloor \frac{n}{d}\right\rfloor g\left(\left\lfloor \frac{m}{d} \right\rfloor\right)\mu(d)[d\perp k]

前面两项可以整除分块，矛盾转移为求后面两项的前缀和，不妨设 f(n)=\sum\limits_{i=1}^n\mu(i)[i\perp k]，继续干苦力活

\begin{aligned} f(n)&=\sum_{i=1}^n\mu(i)[i\perp k] \\ &=\sum_{i=1}^n[i\perp k]f\left(\left\lfloor \frac{n}{i} \right\rfloor\right)-\sum_{i=2}^n[i\perp k]f\left(\left\lfloor \frac{n}{i} \right\rfloor\right)\end{aligned}

考虑前一个怎么求

\begin{aligned}\sum_{i=1}^n[i\perp k]f\left(\left\lfloor \frac{n}{i} \right\rfloor\right)&=\sum_{i=1}^n[i\perp k]\sum_{j=1}^{\lfloor n/i\rfloor}[j\perp k]\mu(j) \\ &=\sum_{i=1}^n\sum_{j=1}^{\lfloor n/i\rfloor}[ij\perp k]\mu(j)\end{aligned}

换一种写法，枚举 ij

\begin{aligned}\sum_{i=1}^n\sum_{j=1}^{\lfloor n/i\rfloor}[ij\perp k]\mu(j)&= \sum_{i=1}^n\sum_{d|i}[i\perp k]\mu(d) \\ &=\sum_{i=1}^n[i\perp k][i=1] \\ &=1\end{aligned}

最终有

f(n)=1-\sum_{i=2}^n[i\perp k]f\left(\left\lfloor\frac{n}{i}\right\rfloor\right)

这个式子就是一个杜教筛的形式，而 [i\perp k] 的前缀和我们已经求出来了，就是 g。

时间复杂度大概是 O(n^{\frac{2}{3}}+k)。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=2005,M=1e6+5;
int n,m,k,mu[M],p[M],v[M],g[N],f[M];
ll ans; map<int,int> ro;

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

void init()
{
    for(int i=1;i<=k;++i) g[i]=g[i-1]+(__gcd(i,k)==1);
    mu[1]=f[1]=1;
    for(int i=2;i<=M-5;++i)
    {
        if(!v[i]) p[++p[0]]=i,mu[i]=-1;
        for(int j=1;j<=p[0]&&i*p[j]<=M-5;++j)
        {
            v[i*p[j]]=1;
            if(i%p[j]==0) break;
            mu[i*p[j]]=-mu[i];
        }
        f[i]=f[i-1]+mu[i]*(G(i)-G(i-1));
    }
}

int F(int x)
{
    if(x<=M-5) return f[x];
    if(ro.find(x)!=ro.end()) return ro[x];
    int res=1;
    for(int l=2,r;l<=x;l=r+1)
        r=x/(x/l),res-=F(x/l)*(G(r)-G(l-1));
    return ro[x]=res;
}

int main()
{
    scanf("%d%d%d",&n,&m,&k),init();
    for(int l=1,r;l<=min(n,m);l=r+1)
    {
        r=min(n/(n/l),m/(m/l));
        ans+=1LL*(n/l)*G(m/l)*(F(r)-F(l-1));
    }
    printf("%lld",ans);
    return 0;
}