洛谷题面

题目大意

给定 \(a,b,d\)，求

\[\sum\limits_{i=1}^a\sum\limits_{j=1}^b[\gcd(i,j)=d] \]

题目分析

令 \(a\le b\)。

显然先把 \(d\) 消掉（令 \(a'=\left\lfloor\dfrac{a}{d}\right\rfloor,b'=\left\lfloor\dfrac{b}{d}\right\rfloor\)）：

\[\sum\limits_{i=1}^{a'}\sum\limits_{j=1}^{b'}[\gcd(i,j)=1] \]

又因为 \(\epsilon(x)=\sum\limits_{d|x}\mu(d)\)。（\(\epsilon(x)=[x=1]\)）

所以

\[\sum\limits_{i=1}^{a'}\sum\limits_{j=1}^{b'}\sum\limits_{x|\gcd(i,j)}\mu(x) \]

\[=\sum\limits_{i=1}^{a'}\sum\limits_{j=1}^{b'}\sum\limits_{x=1}^{a'}\mu(x)\cdot[x|\gcd(i,j)] \]

\[=\sum\limits_{x=1}^{a'}\mu(x)\left\lfloor\dfrac{a'}{x}\right\rfloor\left\lfloor\dfrac{b'}{x}\right\rfloor \]

\[=\sum\limits_{x=1}^{a'}\mu(x)\left\lfloor\dfrac{a}{x\cdot d}\right\rfloor\left\lfloor\dfrac{b}{x\cdot d}\right\rfloor \]

因为是多组询问，所以前面的 \(\sum\limits_{x=1}^{a'}\mu(x)\) 弄个前缀和，后面的 \(\left\lfloor\dfrac{a}{x\cdot d}\right\rfloor\left\lfloor\dfrac{b}{x\cdot d}\right\rfloor\) 整数分块即可。

代码

//2022/1/15

//2022/1/16

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>

#include <cstdio>

#include <climits>//need "INT_MAX","INT_MIN"

#include <cstring>//need "memset"

#include <algorithm>

#define int long long

#define enter() putchar(10)

#define debug(c,que) cerr<<#c<<" = "<<c<<que

#define cek(c) puts(c)

#define blow(arr,st,ed,w) for(register int i=(st);i<=(ed);i++)cout<<arr[i]<<w;

#define speed_up() cin.tie(0),cout.tie(0)

#define endl "\n"

#define Input_Int(n,a) for(register int i=1;i<=n;i++)scanf("%d",a+i);

#define Input_Long(n,a) for(register long long i=1;i<=n;i++)scanf("%lld",a+i);

#define mst(a,k) memset(a,k,sizeof(a))

namespace Newstd
{
	inline int read()
	{
		int x=0,k=1;
		char ch=getchar();
		while(ch<'0' || ch>'9')
		{
			if(ch=='-')
			{
				k=-1;
			}
			ch=getchar();
		}
		while(ch>='0' && ch<='9')
		{
			x=(x<<1)+(x<<3)+ch-'0';
			ch=getchar();
		}
		return x*k;
	}
	inline void write(int x)
	{
		if(x<0)
		{
			putchar('-');
			x=-x;
		}
		if(x>9)
		{
			write(x/10);
		}
		putchar(x%10+'0');
	}
}

using namespace Newstd;

using namespace std;

const int ma=5e4+5;

int p[ma],mu[ma],sum[ma];

bool is[ma];

int T,a,b,d;

int idx;

inline void init(int R)
{
	mu[1]=1,is[1]=true;
	
	for(register int i=2;i<R;i++)
	{
		if(is[i]==false)
		{
			p[++idx]=i;
			
			mu[i]=-1;
		}
		
		for(register int j=1;j<=idx && i*p[j]<R;j++)
		{
			is[i*p[j]]=true;
			
			if(i%p[j]==0)
			{
				mu[i*p[j]]=0;
				
				break;
			}
			
			mu[i*p[j]]=-mu[i];
		}
	}
	
	for(register int i=1;i<R;i++)
	{
		sum[i]=sum[i-1]+mu[i];
	}
}

#undef int

int main(void)
{
	#define int long long
	
	T=read();
	
	init(ma);
	
	while(T--)
	{
		a=read(),b=read(),d=read();
		
		int n=a/d,m=b/d;
		
		if(n<m)//keep n>=m
		{
			swap(n,m);
		}
		
		int res(0);
		 
		for(register int l=1,r;l<=m;l=r+1)
		{
			r=min(n/(n/l),m/(m/l));
			
			res+=(sum[r]-sum[l-1])*((n/l)*(m/l));
		}
		
		printf("%lld\n",res);
	}
	
	return 0;
}