HAOI2011 Problem b

wjh15101051's space

卧薪尝胆，厚积薄发。

HAOI2011 Problem b

Date: Fri Aug 10 22:32:38 CST 2018

In Category: NoCategory

Description：

对于给出的 $n$ 个询问，每次求有多少个数对 $(x,y)$ ，满足 $a\le x\le b$ ， $c\le y\le d$ ，且 $gcd(x,y) = k$ 。

$1\le n \le 50000$

Solution：

先二维前缀和一下，变成 $\sum_{i=1}^n\sum_{j=1}^m[gcd(i,j)==k]$

也就是 $\sum_{i=1}^{\lfloor\frac n k\rfloor}\sum_{j=1}^{\lfloor \frac m k\rfloor}[gcd(i,j)==1]$

$\sum_{i=1}^{n }\sum_{j=1}^{m}[gcd(i,j)==1]=\sum_{i=1}^{n }\sum_{j=1}^{m}\varepsilon(gcd(i,j))$

反演得： $\sum_{i=1}^{n }\sum_{j=1}^{m}\sum_{d|i,d|j}\mu(d)$ ，

交换求和号得： $\sum_{d=1}^{min(n,m)}\sum_{i=1,d|i}^{n}\sum_{j=1,d|j}^{n}1=\sum_{d=1}^{min(n,m)}\lfloor \frac n d\rfloor\lfloor \frac m d\rfloor$

除法分块。

一定注意前缀和是除 $k$ 前的前缀和。

Code：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

#define MAXN 50010

typedef long long ll;

bool isprime[MAXN];

int prime[MAXN],tot = 0;

ll mu[MAXN];

ll sum[MAXN];

void sieve()

{

	for(int i = 2;i < MAXN;++i)isprime[i] = true;

	mu[1] = 1;sum[1] = 1;

	for(int i = 2;i < MAXN;++i)

	{

		if(isprime[i])

		{

			prime[++tot] = i;

			mu[i] = -1;

		}

		for(int j = 1;j <= tot && i * prime[j] < MAXN;++j)

		{

			isprime[i * prime[j]] = false;

			if(i % prime[j] == 0)

			{

				mu[i * prime[j]] = 0;

				break;

			}

			else

			{

				mu[i * prime[j]] = mu[i] * -1;

			}

		}

		sum[i] = sum[i - 1] + mu[i];

	}

	return;

}

ll query(int n,int m)

{

	if(n == 0 || m == 0)return 0;

	ll res = 0;

	for(int l = 1,r;l <= min(n,m);l = r + 1)

	{

		r = min(n / (n / l),m / (m / l));

		res += (ll)(n / l) * (ll)(m / l) * (sum[r] - sum[l - 1]);

	}

	return res;

}

int main()

{

	sieve();

	int n;

	scanf("%d",&n);

	int a,b,c,d,k;

	for(int i = 1;i <= n;++i)

	{

		scanf("%d%d%d%d%d",&a,&b,&c,&d,&k);

		printf("%d\n",query(b / k,d / k) - query((a - 1) / k,d / k) - query(b / k,(c - 1) / k) + query((a - 1) / k,(c - 1) / k));

	}

	return 0;

}

In tag: 数学-莫比乌斯反演

wjh15101051