【Luogu3455】【POI2007】ZAP-Queries（莫比乌斯反演）

题面

题目描述

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

输入输出格式

输入格式：

The first line of the standard input contains one integer nn (1\le n\le 50\ 0001≤n≤50 000),denoting the number of queries.

The following nn lines contain three integers each: aa, bb and dd(1\le d\le a,b\le 50\ 0001≤d≤a,b≤50 000), separated by single spaces.

Each triplet denotes a single query.

输出格式：

Your programme should write nn lines to the standard output. The ii'th line should contain a single integer: theanswer to the ii'th query from the standard input.

输入输出样例

输入样例#1：

2

4 5 2

6 4 3

输出样例#1：

3

2

题解

和前面那一道HDU1695GCD是一样的

直接蒯过代码

然后就会获得70分

这样做的复杂度是\(O(Tn)\)

这题会超时

那么，考虑计算的时候。

\(g(i)=(\frac bk/i)·(\frac dk/i)\)

其中一定会有连续的一段使得\(g(i)\)的值是不会变化的

（Gay神说这叫数论分块，复杂度\(O(\sqrt{n}\)）

因此，预处理出\(\mu\)的前缀和

利用数论分块即可在\(O(T\sqrt{n})的复杂度里计算出来\)

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<set>

#include<map>

#include<vector>

#include<queue>

using namespace std;

#define MAX 101000

inline int read()

{

    int x=0,t=1;char ch=getchar();

    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

    if(ch=='-')t=-1,ch=getchar();

    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

    return x*t;

}

int mu[MAX],pri[MAX],tot,s[MAX];

long long g[MAX],n,a,b,K;

bool zs[MAX];

void Get()

{

    zs[1]=true;mu[1]=1;

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

	{

		if(!zs[i])pri[++tot]=i,mu[i]=-1;

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

		{

			zs[i*pri[j]]=true;

			if(i%pri[j])mu[i*pri[j]]=-mu[i];

			else {mu[i*pri[j]]=0;break;}

		}

	}

	for(int i=1;i<=n;++i)s[i]=s[i-1]+mu[i];

}

long long Calc(int a,int b,int K)

{

	a/=K;b/=K;

	long long ans=0;

	int i=1;

	if(a>b)swap(a,b);

	while(i<=a)

	{

		int j=min(a/(a/i),b/(b/i));

		ans+=1ll*(s[j]-s[i-1])*(a/i)*(b/i);

		i=j+1;

	}

	return ans;

}

int main()

{

	n=100000;

	Get();

	int T=read();

	while(T--)

	{

		a=read();b=read();K=read();

		printf("%lld\n",Calc(a,b,K));

	}

	return 0;

}