【POI2007】ZAP-Queries

题面

题解

$$ \sum_{i=1}^a\sum_{j=1}^b[gcd(i,\;j)=d] \\ =\sum_{i=1}^{\left\lfloor\frac ad\right\rfloor}\sum_{j=1}^{\left\lfloor\frac bd\right\rfloor}[gcd(i,\;j)=1] \\ =\sum_{i=1}^p\mu(i)\lfloor\frac a{id}\rfloor\lfloor\frac b{id}\rfloor $$

筛一下$\mu$即可

代码

#include<bits/stdc++.h>

#define RG register

#define clear(x, y) memset(x, y, sizeof(x));

using namespace std;

inline int read()

{

	int data=0, w=1;

	char ch=getchar();

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

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

	while(ch>='0'&&ch<='9') data=(data<<3)+(data<<1)+(ch^48), ch=getchar();

	return data*w;

}

const int maxn(100010);

int mu[maxn], prime[maxn], cnt, sum[maxn], n=100000, T, a, b, d;

bool not_prime[maxn];

inline void getMu()

{

	not_prime[1]=true; mu[1]=1;

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

	{

		if(!not_prime[i]) prime[++cnt]=i, mu[i]=-1;

		for(RG int j=1;j<=cnt && i*prime[j] <= n;j++)

		{

			not_prime[i*prime[j]]=true;

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

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

		}

	}

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

}

inline long long solve(int a, int b, int d)

{

	a/=d; b/=d;

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

	long long ans=0;

	RG int i=1, j, k, l;

	while(i<=a)

	{

		k=a/i; l=b/i;

		j=min(a/k, b/l);

		ans+=1ll*(sum[j]-sum[i-1])*k*l;

		i=j+1;

	}

	return ans;

}

int main()

{

	getMu();

	T=read();

	while(T--) a=read(), b=read(), d=read(), printf("%lld\n", solve(a, b, d));

	return 0;

}

巴特西

【POI2007】ZAP-Queries

题面

题解

代码

最新文章

热门文章