洛谷题面

题目大意

给定 \(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 

#include 

#include //need "INT_MAX","INT_MIN"

#include //need "memset"

#include 

#define int long long

#define enter() putchar(10)

#define debug(c,que) cerr<<#c<<" = "<'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=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;
}