并不对劲的bzoj2820:p2257:YY的GCD

题目大意

\(t\)(\(t\leq10^4\))组数据，给定\(n,m\)(\(n,m\leq10^6\))求

\[\sum_{x=1}^{n}\sum_{y=1}^{m}[gcd(x,y)=1]
\]

题解

这个人（点这里）讲得很清楚\(\color{white}{\text{shing太强了}}\)

代码

#include<algorithm>

#include<cmath>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<ctime>

#include<iomanip>

#include<iostream>

#include<map>

#include<queue>

#include<set>

#include<stack>

#include<vector>

#define rep(i,x,y) for(register int i=(x);i<=(y);++i)

#define dwn(i,x,y) for(register int i=(x);i>=(y);--i)

#define maxn 10000010

#define lim (maxn-10)

#define LL long long

using namespace std;

int read()

{

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

	while(!isdigit(ch)&&ch!='-')ch=getchar();

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

	while(isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();

	return x*f;

}

void write(LL x)

{

	if(x==0){putchar('0'),putchar('\n');return;}

	int f=0;char ch[20];

	if(x<0)putchar('-'),x=-x;

	while(x)ch[++f]=x%10+'0',x/=10;

	while(f)putchar(ch[f--]);

	putchar('\n');

	return;

}

int t,n,m,p[maxn],no[maxn],mu[maxn],cnt;

LL f[maxn];

int main()

{

	no[1]=mu[1]=1;

	rep(i,2,lim)

	{

		if(!no[i])p[++cnt]=i,mu[i]=-1;

		for(int j=1;j<=cnt&&i*p[j]<=lim;j++)

		{

			no[i*p[j]]=1;

			if(i%p[j]==0){mu[i*p[j]]=0;break;}

			mu[i*p[j]]=-mu[i];

		}

	}

	rep(i,1,cnt)for(int j=p[i];j<=lim;j+=p[i])f[j]+=mu[j/p[i]];

	rep(i,1,lim)f[i]+=f[i-1];

	t=read();

	while(t--)

	{

		n=read(),m=read();

		if(n>m)swap(n,m);LL ans=0;

		for(int l=1,r=0;l<=n;l=r+1)r=min(n/(n/l),m/(m/l)),ans+=(LL)(n/l)*(LL)(m/l)*(f[r]-f[l-1]);

		write(ans);

	}

	return 0;

}

巴特西

并不对劲的bzoj2820:p2257:YY的GCD

题目大意

题解

代码

最新文章

热门文章