题解 P3455 【[POI2007]ZAP-Queries】

· · 个人记录

求

Ans=\sum_{i=1}^N\sum_{j=1}^M[(i,j)=t]

先上套路

f(n)=\sum_{i=1}^N\sum_{j=1}^M[(i,j)=n] F(n)=\left \lfloor \frac{N}{n} \right \rfloor\times\left \lfloor \frac{M}{n} \right \rfloor=\sum_{n|d}f(d)

我们要求的就是f(t)

f(n)=\sum_{n|d}\mu(\frac{d}{n})F(d)=\sum_{n|d}\mu(\frac{d}{n})\times \left \lfloor \frac{N}{d} \right \rfloor\times\left \lfloor \frac{M}{d} \right \rfloor

把后面的提出来

\sum_{n|d}\mu(\frac{d}{n})\times \left \lfloor \frac{N}{d} \right \rfloor\times\left \lfloor \frac{M}{d} \right \rfloor=\sum_{i=1}^N\left \lfloor \frac{N}{i} \right \rfloor\times\left \lfloor \frac{M}{i} \right \rfloor\sum_{n|i}\mu(\frac{i}{n})

前面分块后面前缀和就好了

但是很快就发现不对了，后面那个东西根本没法前缀和，因为每一次的n都是变的

但是别忘了gcd有一个神奇的性质啊

如果(a,b)=1，那么就存在(a\times d,b\times d)=d啊

所以我们要求

\sum_{i=1}^N\sum_{j=1}^M[(i,j)=d]

可以直接求

\sum_{i=1}^{\left \lfloor \frac{N}{d} \right \rfloor}\sum_{j=1}^{\left \lfloor \frac{M}{d} \right \rfloor}[(i,j)=1]

就好了

这样这些互质的数对乘上d就是(i,j)=d了

所以就相当于上面的柿子里n=1，N=\left \lfloor \frac{N}{d} \right \rfloor,M=\left \lfloor \frac{M}{d} \right \rfloor就好了

#include<iostream>
#include<cstring>
#include<cstdio>
#define re register
#define maxn 50005
#define LL long long
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
inline int read()
{
    char c=getchar();
    int x=0;
    while(c<'0'||c>'9') c=getchar();
    while(c>='0'&&c<='9')
        x=(x<<3)+(x<<1)+c-48,c=getchar();
    return x;
}
int p[maxn>>1],mu[maxn],f[maxn];
LL pre[maxn];
int n,m,d,t,T;
int main()
{
    f[1]=1,mu[1]=1;
    for(re int i=2;i<=50000;i++)
    {
        if(!f[i]) p[++p[0]]=i,mu[i]=-1;
        for(re int j=1;j<=p[0]&&p[j]*i<=50000;j++)
        {
            f[p[j]*i]=1;
            if(i%p[j]==0) break;
            mu[p[j]*i]=-1*mu[i];
        }
    }
    for(re int i=1;i<=50000;i++) pre[i]+=pre[i-1]+mu[i];
    T=read();
    while(T--)
    {
        n=read(),m=read(),t=read();
        if(n>m) std::swap(n,m);
        n/=t,m/=t;
        LL ans=0;
        for(re int l=1,r;l<=n;l=r+1)
        {
            r=min(n/(n/l),m/(m/l));
            ans+=(LL)(n/l)*(m/l)*(pre[r]-pre[l-1]);
        }
        printf("%lld\n",ans);
    }
    return 0;
}