首页 > 代码库 > 【BZOJ】2820: YY的GCD(莫比乌斯)

【BZOJ】2820: YY的GCD(莫比乌斯)

http://www.lydsy.com/JudgeOnline/problem.php?id=2820

此题非常神!

下文中均默认n<m

首先根据bzoj1101的推理,我们易得对于一个数d使得数对(x,y)=k的个数为:

$$\sum_{1<=d<=n‘} \mu (d) \times \lfloor \frac{n}{d} \rfloor \times \lfloor \frac{m}{d} \rfloor, 其中n‘=\lfoor \frac{n}{k} \rfloor$$

所以本题很容易得到

$$\sum_{p是质数}^{n} \sum_{1<=d<=n/p} \mu (d) \times \lfloor \frac{n/p}{d} \rfloor \times \lfloor \frac{m/p}{d} \rfloor$$

因为整除取下界可以有结合律(有待证明),所以设$T=pd$,那么问题可以转换为:

$$\sum_{p是质数}^{n} \sum_{1<=d<=n/p} \mu (d) \times \lfloor \frac{n}{T} \rfloor \times \lfloor \frac{m}{T} \rfloor$$

将问题转换为枚举T(考虑$T=1$的情况也无妨,因为最终不会计入),得:

$$\sum_{T=1}^{n} \sum_{p<=n且p|T} \mu (\frac{T}{p}) \times \lfloor \frac{n}{T} \rfloor \times \lfloor \frac{m}{T} \rfloor$$

化简得

$$\sum_{T=1}^{n} \lfloor \frac{n}{T} \rfloor \times \lfloor \frac{m}{T} \rfloor \sum_{p<=n且p|T} \mu (\frac{T}{p})$$

设$g[x]=\sum_{p<=n且p|x} \mu (\frac{x}{p})$

那么原式变成

$$\sum_{T=1}^{n} \lfloor \frac{n}{T} \rfloor \times \lfloor \frac{m}{T} \rfloor \times g[T]$$

真漂亮的公式!

那么我们只需要考虑如何计算g[x]即可!而且如果$p不是质数或者p \nmid T$,那么$g[x]=0$

我们发现$g[x]$似乎可以在线性筛的时候预处理出?$x=k \times p, p为质数$的情况,可得:

$$

g[kp]=

\begin{cases}

\mu (k) & 当p|k时 \

\mu (k) - g[k] & 当p \nmid k时\

\end{cases}

$$

首先根据定义,此时

$$g[kp]=\sum_{p‘<=n且p‘|kp} \mu (\frac{kp}{p‘})$$

为什么呢?

首先考虑$p|k$时,有$kp$质因子$p$的指数>=2

1、当$p‘=p$,那么约掉后还剩下$\mu (k)$

2、当$p‘ \neq p$,那么$p$的质数>=2,根据莫比乌斯函数的定义,为0

因此$式1+式2=\mu (k)$

考虑$p \nmid k$时,有$kp$质因子$p$的指数=1

1、当$p‘=p$,那么约掉后同样是$\mu (k)$

2、当$p‘ \neq p$,那么因为$\mu$是积性函数,且$p与\frac{k}{p‘}$互质,那么得到$\mu(p) \frac{k}{p‘}$,然后提出和式。因为$\mu(p)=-1$,而和式内的和恰好就是$g[k]$的定义,因此这种情况的个数为$-g[k]$

因此$式1+式2=-g[k]$

然后和1101一样的做法了,分块然后乘起来。。

#include <cstdio>#include <cstring>#include <cmath>#include <string>#include <iostream>#include <algorithm>#include <queue>#include <set>#include <map>using namespace std;typedef long long ll;#define rep(i, n) for(int i=0; i<(n); ++i)#define for1(i,a,n) for(int i=(a);i<=(n);++i)#define for2(i,a,n) for(int i=(a);i<(n);++i)#define for3(i,a,n) for(int i=(a);i>=(n);--i)#define for4(i,a,n) for(int i=(a);i>(n);--i)#define CC(i,a) memset(i,a,sizeof(i))#define read(a) a=getint()#define print(a) printf("%d", a)#define dbg(x) cout << (#x) << " = " << (x) << endl#define error(x) (!(x)?puts("error"):0)inline const int getint() { int r=0, k=1; char c=getchar(); for(; c<‘0‘||c>‘9‘; c=getchar()) if(c==‘-‘) k=-1; for(; c>=‘0‘&&c<=‘9‘; c=getchar()) r=r*10+c-‘0‘; return k*r; }#define rdm(x, i) for(int i=ihead[x]; i; i=e[i].next)const int N=10000005;int p[N], cnt, np[N], mu[N], g[N], sum[N];void init() {	mu[1]=1;	for2(i, 2, N) {		if(!np[i]) p[++cnt]=i, mu[i]=-1, g[i]=1;		for1(j, 1, cnt) {			int t=p[j]*i; if(t>=N) break;			np[t]=1;			if(i%p[j]==0) { mu[t]=0; g[t]=mu[i]; break; }			mu[t]=-mu[i]; g[t]=mu[i]-g[i];		}	}	for2(i, 1, N) sum[i]=sum[i-1]+g[i];}int main() {	int t=getint(); init();	while(t--) {		int n=getint(), m=getint();		ll ans=0; if(n>m) swap(n, m);		int pos;		for(int i=1; i<=n; i=pos+1) {			pos=min(n/(n/i), m/(m/i));			ans+=(ll)(sum[pos]-sum[i-1])*(n/i)*(m/i);		}		printf("%lld\n", ans);	}	return 0;}

  

 


 

 

Description

神犇YY虐完数论后给傻×kAc出了一题
给定N, M,求1<=x<=N, 1<=y<=M且gcd(x, y)为质数的(x, y)有多少对
kAc这种傻×必然不会了,于是向你来请教……
多组输入

Input

第一行一个整数T 表述数据组数
接下来T行,每行两个正整数,表示N, M

Output

T行,每行一个整数表示第i组数据的结果

Sample Input

2
10 10
100 100

Sample Output

30
2791

HINT

 

T = 10000

N, M <= 10000000

 

Source

【BZOJ】2820: YY的GCD(莫比乌斯)