题目要求
\[\sum_{x=1}^a\sum_{y=1}^b[gcd(a,b)=d]\]
设上式为\(f(d)\),构造\(g(n)=\sum_{n|d}f(d)\),于是有
\[g(n)=\sum_{x=1}^a\sum_{y=1}^b[n|gcd(a,b)]\]
易得
\[g(d)=\lfloor\frac{a}{d}\rfloor\lfloor\frac{b}{d}\rfloor\]
代入反演一下
\[f(n)=\sum_{n|d}\mu(\frac{d}{n})\lfloor\frac{a}{d}\rfloor\lfloor\frac{b}{d}\rfloor\]
令\(t=\frac{d}{n}\),代入得
\[f(n)=\sum_{t=1}^\frac{min(a,b)}{n}\mu(t)\lfloor\frac{a}{nt}\rfloor\lfloor\frac{b}{nt}\rfloor\]
预处理\(\mu\)的前缀和,整除分块即可
#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#define maxn 50005
#define N 50000
using namespace std;
typedef long long ll;
template <typename T> void read(T &t)
{
t=0;int f=0;char c=getchar();
while(!isdigit(c)){f|=c=='-';c=getchar();}
while(isdigit(c)){t=t*10+c-'0';c=getchar();}
if(f)t=-t;
}
int n;
int pri[maxn],pcnt,nop[maxn],mu[maxn];
int a,b,k;
void GetPrime()
{
mu[1]=1,nop[1]=1;
for(register int i=2;i<=N;++i)
{
if(!nop[i])pri[++pcnt]=i,mu[i]=-1;
for(register int j=1;j<=pcnt && i*pri[j]<=N;++j)
{
nop[i*pri[j]]=1;
if(i%pri[j]==0)break;
else mu[i*pri[j]]=-mu[i];
}
}
for(register int i=1;i<=N;++i)mu[i]+=mu[i-1];
}
int Calc()
{
int re=0,up=min(a,b)/k;
for(register int l=1,r;l<=up;l=r+1)
{
r=min(a/(a/l),b/(b/l));
re+=(mu[r]-mu[l-1])*(a/(l*k))*(b/(l*k));
}
return re;
}
int main()
{
GetPrime();
read(n);
while(n--)
{
read(a),read(b),read(k);
printf("%d\n",Calc());
}
return 0;
}
「Luogu3455」[POI2007]ZAP-Queries
原文:https://www.cnblogs.com/lizbaka/p/10513433.html