题解 P3455 【[POI2007]ZAP-Queries】

· · 题解

【题解】Zap(莫比乌斯反演)

好像没有我这样化的，发一波题解

传送门

所有除法默认向下取整

\Sigma_{i=1}^x\Sigma_{j=1}^y[(i,j)=k] =\Sigma_{i=1}^{x/k}\Sigma_{j=1}^{y/k}[(i,j)=1] =\Sigma_{i=1}^{x/k}\Sigma_{j=1}^{y/k}\Sigma_{d|(i,j)}\mu(d) =\Sigma_{d=1}^{min(x,y)}\Sigma_{i=1}^{x/k}\Sigma_{j=1}^{y/k}\mu(d)\times[d|(i,j)] =\Sigma_{d=1}^{min(x,y)}(\frac x {dk})(\frac y {dk})\mu(d)

整除分块直接做...

有一个细节，可能有疑惑：

    r=min(x/(x/l),y/(y/l));
    ans+=1ll*(x/(l*k))*(y/((l*k)))*(sum[r]-sum[l-1]);

整除分块为什么是这样的？为什么"r=min(x/(x/l),y/(y/l));"中的"l"和"ans+=1ll*(x/(l*k))*(y/((l*k)))*(sum[r]-sum[l-1]);"不统一，为什么是"(x/(l*k))*(y/(l*k))"这不是整除分块正常的套路啊？

可以这样理解，整除分块利用了\lfloor \frac x l \rfloor在一定范围内不变的性质，所以我们同样也会有\lfloor\frac {\lfloor \frac x l \rfloor} k\rfloor在一定范围内不变化，并且前面那个式子包括的l的范围一定小于后面的那个l的范围，所以我们按照\lfloor \frac x l \rfloor整除分块即可。

至于如何按照\lfloor\frac {\lfloor \frac x l \rfloor} k\rfloor=\lfloor \frac x {lk} \rfloor分块(复杂度更加优秀?)，我也不知道怎么办，希望有高手指点一下QAQ

#include<bits/stdc++.h>

using namespace std;typedef long long ll;
template < class ccf >
 inline ccf qr(ccf b){
    register char c=getchar();register int q=1;register ccf x=0;
    while(c<48||c>57)q=c==45?-1:q,c=getchar();
    while(c>=48&&c<=57)x=x*10+c-48,c=getchar();
    return q==-1?-x:x;}
inline int qr(){return qr(1);}
const int maxn=1e5+5;
bool usd[maxn];
int mu[maxn];
int sum[maxn];
vector < int > ve;
int x,y,k;
#define pb push_back
inline void gen(){
    mu[1]=sum[1]=usd[1]=1;
    for(register int t=2;t< maxn;++t){
    if(not usd[t])
        ve.pb(t),mu[t]=-1;
    for(register auto p:ve)
        if(1ll*p*t<maxn)
        if(usd[p*t]=1,t%p) mu[p*t]=-mu[t];
        else break;
        else break;
    sum[t]=sum[t-1]+mu[t];
    }
}

int main(){
    gen();
    int T=qr();
    while(T--){
    x=qr();y=qr();k=qr();
    ll ans=0;
    for(register int l=1,r=0,edd=min(x,y)/k;l<=edd;l=r+1){
        r=min(x/(x/l),y/(y/l));
        ans+=1ll*(x/(l*k))*(y/((l*k)))*(sum[r]-sum[l-1]);
    }
    cout<<ans<<endl;
    }
    return 0;
}