洛谷P3455 ZAP-Queries [POI2007] 莫比乌斯反演+数论分块

时间：2023-03-08 18:56:26

正解:莫比乌斯反演

解题报告:

传送门!

首先这题刚看到就很,莫比乌斯反演嘛,和我前面写了题解的那个一模一样的,所以这儿就不讲这前边的做法辣QAQ

但是这样儿还有个问题,就现在已知我每次都是要O(n)地做的,然后他还有Q个问题,这样复杂度显然就假了,就要想办法优化QAQ

这时候考虑到我们已经搞出来要求的式子长这样儿:$\sum \mu[i]\cdot \left \lfloor \frac{m}{i}\right \rfloor\cdot\left \lfloor \frac{n}{i} \right \rfloor$,这就很,整除分块昂!

所以预处理$\mu $的时候顺便搞下前缀和,整除分块就能过去辣!

#include<bits/stdc++.h>

using namespace std;

#define il inline

#define ll long long

#define gc getchar()

#define t(i) edge[i].to

#define w(i) edge[i].wei

#define fy(i) edge[i].fy

#define ri register int

#define rb register bool

#define rc register char

#define lb(x) lower_bound(st+1,st+1+st_cnt,x)-st-1

#define rp(i,x,y) for(ri i=x;i<=y;++i)

#define my(i,x,y) for(ri i=x;i>=y;--i)

#define e(i,x) for(ri i=head[x];~i;i=edge[i].nxt)

const int N=+;

int n,m,miu[N],sum[N],pr[N],pr_cnt;

bool is_pr[N];

il int read()

{

    rc ch=gc;ri x=;rb y=;

    while(ch!='-' && (ch<'' || ch>''))ch=gc;

    if(ch=='-')ch=gc,y=;

    while(ch>='' && ch<='')x=(x<<)+(x<<)+(ch^''),ch=gc;

    return y?x:-x;

}

il void pre()

{

    sum[]=miu[]=;

    rp(i,,N-)

    {

        if(!is_pr[i])miu[i]=-,pr[++pr_cnt]=i;sum[i]=sum[i-]+miu[i];

        rp(j,,pr_cnt){if(pr[j]*i>N-)break;is_pr[i*pr[j]]=;if(!(i%pr[j])){miu[i*pr[j]]=;break;}else miu[i*pr[j]]=-miu[i];}

    }

}

il ll cal(ri x,ri y,ri z)

{

    x/=z;y/=z;ll ret=;

    for(ri i=,j;i<=min(x,y);i=j+){j=min(x/(x/i),y/(y/i));ret+=1ll*(sum[j]-sum[i-])*(x/i)*(y/i);}

    return ret;

}

int main()

{

//    freopen("3455.in","r",stdin);freopen("3455.out","w",stdout);

    pre();

    int T=read();

    while(T--){ri a=read(),b=read(),k=read();printf("%lld\n",cal(a,b,k));}

    return ;

}

放下代码QwQ

相关文章