bzoj 4562 [NOI2016]循环之美 莫比乌斯反演

几年没写题解来更一篇。
首先有一个规律就是如果满足条件那么$gcd(y,k)=1$
那么答案就是
$\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}[gcd(i,j)=1][gcd(j,k)=1]$
$=\sum\limits_{j=1}^{m}[gcd(j,k)=1]\sum\limits_{i=1}^n\sum\limits_{t|i,t|j}\mu(t)$
$=\sum\limits_{t=1}^{m}\mu(t)*\lfloor{\frac{n}{t}}\rfloor\sum\limits_{j=1}^{\frac{m}{t}}[gcd(tj,k)=1]$
$==\sum\limits_{t=1}^{m}\mu(t)*\lfloor{\lfloor\frac{n}{t}\rfloor}\rfloor[gcd(t,k)=1]\sum\limits_{j=1}^{\lfloor\frac{m}{t}\rfloor}[gcd(j,k)=1]$
$O(\sqrt{n})$ 枚举$\lfloor\frac{n}{t}\rfloor,\lfloor\frac{m}{t}\rfloor$
对于每段$\sum\limits_{j=1}^{x}[gcd(j,k)=1]=\sum\limits_{r|k}\mu(r)*\lfloor\frac{x}{r}\rfloor$ 直接算就行了。
设k的质因数分解为$p_1^{a_1}p_2^{a_2}....p_{cnt}^{a_{cnt}}$，$k_i=p_1^{a_1}p_2^{a_2}....p_i^{a_i}$
设$f(i,x)=\sum\limits_{t=1}^{x}\mu(t)[gcd(t,k_i)=1]$
那么要求的是$f(cnt,x)$
$f(i,x)=\sum\limits_{t=1}^{x}\mu(t)[gcd(t,k_i)=1]$
$=\sum\limits_{t=1}^{x}\mu(t)[gcd(t,k_{i-1}p_i^{a_i})=1]$
$=\sum\limits_{t=1}^{x}\mu(t)[gcd(t,k_{i-1})=1][gcd(t,p_i)=1]$
$=\sum\limits_{t=1}^{x}\mu(t)[gcd(t,k_{i-1})=1]-\sum\limits_{p_i|t}\mu(t)[gcd(t,k_{i-1})=1]$
$=\sum\limits_{t=1}^{x}\mu(t)[gcd(t,k_{i-1})=1]-\sum\limits_{t=1}^{\lfloor\frac{x}{p_i}\rfloor}\mu(t*p_i)[gcd(t*p_i,k_{i-1})=1]$
$=\sum\limits_{t=1}^{x}\mu(t)[gcd(t,k_{i-1})=1]-\sum\limits_{t=1}^{\lfloor\frac{x}{p_i}\rfloor}\mu(t*p_i)[gcd(t,k_i)=1]$
然后第二段中如果$t\%p_i=0$ 没有贡献，否则当$gcd(t,p_i)=1$ 时$\mu(t*p_i)=-\mu(t)$
因此上式
$=\sum\limits_{t=1}^{x}\mu(t)[gcd(t,k_{i-1})=1]+\sum\limits_{t=1}^{\lfloor\frac{x}{p_i}\rfloor}\mu(t)[gcd(t,k_i)=1]$
$=f(i-1,x)+f(i,\lfloor\frac{x}{p_i}\rfloor)$
当$i=0$ 时 $f(i,x)$ 可以通过杜教筛计算。
然后这个杜教筛就是把$\sum\limits_{i=1}^{\lfloor\frac{n}{x}\rfloor}\mu(i)$ 算一遍。
因此复杂度大概是$O(\sqrt{min(n,m)}*(\sqrt{k}+logn)+n^\frac{2}{3}logn)$

Orz 小火车

#include <bits/stdc++.h>
using namespace std;
#define N 5100000
#define A 5000000
#define ll long long
ll ans;
int n,m,K,cnt,cnt1;
int mu[N],prime[N],ip[N],sum[N],p[11],p1[110];
map<pair<int,int>,int>ma1;
map<int,int>ma2;
void init()
{
    mu[1]=1;
    for(int i=2;i<=A;i++)
    {
        if(!ip[i]){prime[++cnt]=i;mu[i]=-1;}
        for(int j=1;j<=cnt&&i*prime[j]<=A;j++)
        {
            ip[i*prime[j]]=1;
            if(i%prime[j]==0)break;
            mu[i*prime[j]]=-mu[i];
        }
    }
    for(int i=1;i<=A;i++)
        sum[i]=sum[i-1]+mu[i];
    cnt=0;
    for(int i=1;i<=K;i++)
        if(K%i==0)p1[++cnt1]=i;
    for(int i=1;prime[i]<=K;i++)
        if(K%prime[i]==0)p[++cnt]=prime[i];
}
int djs(int x)
{
    if(x<=A)return sum[x];
    if(ma2.count(x))return ma2[x];
    int ret=1;
    for(int i=2,last;i<=x;i=last+1)
    {
        last=x/(x/i);
        ret-=djs(x/i)*(last-i+1);
    }
    return ma2[x]=ret;
}
int cal1(int x,int y)
{
    if(y==0)return 0;
    if(x==0)return djs(y);
    pair<int,int> t=make_pair(x,y);
    if(ma1.count(t))return ma1[t];
    int ret=cal1(x-1,y)+cal1(x,y/p[x]);
    return ma1[t]=ret;
}
int cal2(int x)
{
    int ret=0;
    for(int i=1;i<=cnt1;i++)
        ret+=mu[p1[i]]*(x/p1[i]);
    return ret;
}
int main()
{
    scanf("%d%d%d",&n,&m,&K);
    init();
    for(int i=1,last;i<=m&&i<=n;i=last+1)
    {
        last=min(n/(n/i),m/(m/i));
        ans+=(ll)(cal1(cnt,last)-cal1(cnt,i-1))*(n/i)*cal2(m/i);
    }
    printf("%lld\n",ans);
    return 0;
}