并不对劲的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; }

转载于:https://www.cnblogs.com/xzyf/p/10448607.html

总结

以上是生活随笔为你收集整理的并不对劲的bzoj2820:p2257:YY的GCD的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。