Bzoj1101 [poi2007]zap

Posted by yjjr's blog on December 12, 2017

标签:莫比乌斯反演

题目

题目传送门

Description

  FGD正在破解一段密码,他需要回答很多类似的问题:对于给定的整数a,b和d,有多少正整数对x,y,满足x<=a ,y<=b,并且gcd(x,y)=d。作为FGD的同学,FGD希望得到你的帮助。 Input

  第一行包含一个正整数n,表示一共有n组询问。(1<=n<= 50000)接下来n行,每行表示一个询问,每行三个 正整数,分别为a,b,d。(1<=d<=a,b<=50000) Output

  对于每组询问,输出到输出文件zap.out一个正整数,表示满足条件的整数对数。 Sample Input 2

4 5 2

6 4 3 Sample Output 3

2

//对于第一组询问,满足条件的整数对有(2,2),(2,4),(4,2)。对于第二组询问,满足条件的整数对有(

6,3),(3,3)。

分析

第一次做莫比乌斯反演的题目

令$a’=\lfloor a/d\rfloor ,b’=\lfloor b/d\rfloor$

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

$=\sum_{i=1}^a’\sum_{j=1}^b’ [gcd(i,j)==1]$

可以利用莫比乌斯函数的性质,把上面的求和式转化

$=\sum_{i=1}^a’\sum_{j=1}^b’\sum_{d gcd(i,j)} \mu (d)$

我们可以把第三个下标变化

$=\sum_{i=1}^a’\sum_{j=1}^b’\sum_{d i\ and\ d j}$

$=\sum_{d=1}^{\min (a’,b’)}\mu(d) \lfloor a/d \rfloor \lfloor b/d \rfloor$

比如$a’=100$,那么$d在[34,50]之间a’/d都是2。$

设$a’/d=x$,那么最后一个$a’/d=x$的$d=a’/x$,所以这段连续的区间就是$[d,a’/(a’/d)]$

那么可以分块处理:一个块内的和可以用预处理出的莫比乌斯函数前缀和求出

code

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
using namespace std;
inline ll read()
{
	ll f=1,x=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
const int maxn=50006;
int cnt=0,mu[maxn],sum[maxn],prime[maxn];
bool is_prime[maxn];
int cal(int n,int m)
{
	if(n>m)swap(n,m);
	int ans=0,pos;
	for(int i=1;i<=n;i=pos+1){
		pos=min(n/(n/i),m/(m/i));
		ans+=(sum[pos]-sum[i-1])*(n/i)*(m/i);
	}
	return ans;
}

int main()
{
	mu[1]=1;
	rep(i,2,maxn-6){
		if(!is_prime[i])prime[++cnt]=i,mu[i]=-1;
		rep(j,1,cnt){
			if(i*prime[j]>maxn-6)break;
			is_prime[prime[j]*i]=1;
			if(i%prime[j]==0){mu[i*prime[j]]=0;break;}
			else mu[i*prime[j]]=-mu[i];
		}
	}
	rep(i,1,maxn-6)sum[i]=sum[i-1]+mu[i];
	int Que=read();
	while(Que--){
		int a=read(),b=read(),d=read();
		printf("%d\n",cal(a/d,b/d));
	}
	return 0;
}
本文可以转载,但必须附上原文链接,否则你会终生找不到妹子!!!欢迎关注我的CSDN: ahyjjr