Kelin的题解

略解

根据题意,为了去重,取最简 $\frac{x}{y}$ ,即 $(x,y)=1$。

设循环节为 $l$ ,则 $\frac{xk^l}{y}-\lfloor\frac{xk^l}{y}\rfloor=\frac{x}{y}-\lfloor\frac{x}{y}\rfloor$

$xk^l\equiv x(\text{mod}~y)$

$k^l\equiv 1(\text{mod y})$

根据裴蜀定理,当且仅当 $(k^l,y)=1$ ,即 $(k,y)=1$ 时,$k$有正整数解。

那么转化完之后,

就是让我们求

$\begin{aligned}\sum\limits_{i=1}^n\sum\limits_{j=1}^m [(i,j)=1][(j,k)=1]&=\sum_{d=1}^{\min(n,m)}\mu(d)\lfloor\frac{n}{d}\rfloor\sum\limits_{j=1}^m [d\mid j][(j,k)=1]\\&=\sum_{d=1}^{\min(n,m)}\mu(d)\lfloor\frac{n}{d}\rfloor\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}[(jd,k)=1]\\&=\sum_{d=1}^{\min(n,m)}\mu(d)[(d,k)=1]\lfloor\frac{n}{d}\rfloor\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}[(j,k)=1]\end{aligned}$

$ f(n)=\sum\limits_{i=1}^{n}[(i,k)=0]=\lfloor\frac{n}{k}\rfloor f(k)+f(n~\text{mod}~ k)$

$g(n,k)=\sum\limits_{d=1}^{n}\mu(d)[(d,k)=1]$

到这一步有两种做法。

做法1

$\begin{aligned}g(n,k)&=\sum_{d=1}^n\mu(d)\sum_{p\mid k}[p\mid d]\mu(p)\\&=\sum_{p|k}\mu(p)\sum_{p|d}\mu(d)\\&=\sum_{p|k}\mu(p)\sum_{d=1}^{\lfloor\frac{n}{d}\rfloor }\mu(dp)\end{aligned}$

由于 $\mu(dp)=\mu(d)\mu(p)\ne 0$ 的条件为$(d,p)=1$

$\begin{aligned}g(n,k)&=\sum_{p|k}\mu(p)^2\sum_{d=1}^{\lfloor\frac{n}{p}\rfloor }\mu(d)[(d,p)=0]\\&=\sum_{p|k}\mu(p)^2g(\lfloor\frac{n}{p}\rfloor,p) \end{aligned}$

边界$g(n,1)=\sum\limits_{i=1}^n \mu(i)$,杜教筛。

做法2

$k=p^aq$,$p$为最小$k$的质因数。

可以容斥一下

$\begin{aligned}g(n,k)&=\sum_{d=1}^n\mu(d)[(d,q)=1]-\sum_{d=1}^n\mu(d)[(d,q)=1][(d,p)=1]\\&=g(n,q)-\sum_{d=1}^{\lfloor\frac{n}{p}\rfloor}\mu(dp)[(dp,q)=1]\\&=g(n,q)-\mu(p)\sum_{d=1}^{\lfloor\frac{n}{p}\rfloor}\mu(d)[(d,q)=1][(d,p)=1]\\&=g(n,q)+g(\lfloor\frac{n}{p}\rfloor,k)\end{aligned}$

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<ctime>
#include<map>
#include<cstdlib>
#include<vector> 
#define gc getchar()
#define ll long long
#define ull unsigned long long
#define file(s) freopen(s".in","r",stdin);freopen(s".out","w",stdout)
#define I inline 
using namespace std;
const int N=1e6+5,mod=2e6+7;
const ull p0=31,p1=37;
template<class o>I void qr(o &x)
{
    char c=gc;int f=1;x=0;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
template<class o>I void qw(o x)
{
    if(x<0)x=-x,putchar('-');
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
struct edge{int n,k,w,next;}a[mod<<1];int len,last[mod];
int mu[N],prime[N],f[2005],smu[N],cnt=0,M=1e6;bool v[N];
int gcd(int a,int b){return !b?a:gcd(b,a%b);}
void init()
{
    mu[1]=1;
    for(int i=2;i<=M;++i)
    {
        if(!v[i])prime[++cnt]=i,mu[i]=-1;
        for(int j=1;j<=cnt&&i*prime[j]<=M;++j)
        {
            v[i*prime[j]]=1;
            if(i%prime[j]==0){mu[i*prime[j]]=0;break;}
            mu[i*prime[j]]=-mu[i];
        }
    }
    for(int i=1;i<=M;i++)smu[i]=smu[i-1]+mu[i];
}
int p[N],q[N];
int g(int n,int k)
{
    if(!n||(n<=M&&k==1))return smu[n];
    int z=(1ll*n*2017+k)%mod;
    for(int i=last[z];i;i=a[i].next)if(a[i].n==n&&a[i].k==k)return a[i].w;
    a[++len]=(edge){n,k,0,last[z]};last[z]=len;int &w=a[len].w;
    if(k==1)
    {
        w=1;int l=2,r=sqrt(n),x;
        for(;l<=r;++l)w-=g(n/l,1);
        for(;l<=n;l=r+1)x=n/l,r=n/x,w-=(r-l+1)*g(x,1);
    }
    else w=g(n,q[k])+g(n/p[k],k);
    return w;
}
int n,m,k;
I int F(int x){return (x/k)*f[k]+f[x%k];}
int main()
{
    qr(n),qr(m),qr(k);
    M=min(N-5,max(k,min(n,m)));init();
    for(int i=1;i<=k;i++)f[i]=f[i-1]+(gcd(i,k)==1);
    for(int i=2;i<=k;i++)
    {
        for(int j=1;;++j)if(i%prime[j]==0){p[i]=prime[j];break;}
        for(q[i]=i;q[i]%p[i]==0;)q[i]/=p[i];
    }
    int l=1,r=sqrt(min(n,m)),x,y,s,t=0;ll ans=0;
    for(;l<=r;++l,t=s)s=g(l,k),ans+=1ll*(n/l)*F(m/l)*(s-t);
    for(;l<=min(n,m);l=r+1,t=s)x=n/l,y=m/l,r=min(n/x,m/y),
        s=g(r,k),ans+=1ll*x*F(y)*(s-t);
    qw(ans);puts("");
    return 0;
}