P2257 YY的GCD

解题思路

果然数论的题是真心不好搞。

第一个莫比乌斯反演的题，好好推一下式子吧。。（借鉴了）

我们要求的答案就是\(Ans=\sum\limits_{i=1}^{n}\sum\limits _{j=1}^{m}[\gcd(x,y)=prim]\)

这算是一类题了，大概套路如下：

• \(f[d]\) 表示 \(\gcd(i,j)\) 所有的方案数。

  即：\(f(d)=\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}[gcd(i,j)=d]\)

• \(F(n)\) 为 \(\gcd(i,j)=n\) 和 \(n\) 的倍数的个数

  即：\(F(n)=\sum\limits_{n|d}f(d)=\lfloor\frac{N}{n}\rfloor\lfloor\frac{M}{n}\rfloor\)

  也就是N中为n的倍数的数目与M中为n的倍数的数目的乘积就是所求的 F(n) 了。

• 根据以上的定义，莫比乌斯反演不难得出:

  \(f(n)=\sum\limits_{n|d}\mu(\lfloor\frac{d}{n}\rfloor)F(d)\)
  接下来就是化简式子了

\(Ans=\sum\limits_{p\in prim}\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}[gcd(i,j)=p]\)

将\(f(p)\)带入上面式子：

\(Ans=\sum\limits_{p\in prim}f(p)\)

再用上面的式子3莫比乌斯反演一下:

\(Ans=\sum\limits_{p\in prim}\sum\limits_{p|d}\mu(\lfloor\frac{d}{p}\rfloor)F(d)\)

将之前给出的\(F(n)\)表达式带入，再更改一下循环顺序：

\(Ans=\sum\limits_{T=1}^{min(n,m)}\sum\limits_{t|T,t\in prime}\mu(\lfloor\frac{T}{t}\rfloor)\lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor\)

\(Ans=\sum\limits_{T=1}^{min(n,m)}\lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor(\sum\limits_{t|T,t\in prime}\mu(\lfloor\frac{T}{t}\rfloor))\)

最后，数论分块一下求一个前缀和就好了。

数论分块：
对于任意一个\(i(i \le n)\)，我们需要找到一个最大的 \(j(i \le j \le n )\)，使得
此时

• 注意：只有ans开 long long就好了，都开的话会TLE

code

#include
//#define int long long
using namespace std;
const int N=1e7+10;
int T,n,m,ans;
int cnt,f[N],sum[N],mu[N],pri[N];
bool vis[N];
void get_Mobius()
{
	mu[1]=1;
	for(int i=2;im)
			swap(n,m);
		for(int l=1,r;l<=n;l=r+1)
		{
			r=min(n/(n/l),m/(m/l));
			ans+=1ll*(n/l)*(m/l)*(sum[r]-sum[l-1]);
		}
		printf("%lld\n",ans);
	}
	return 0;
}