- BZOJ2818: Gcd https://www.lydsy.com/JudgeOnline/problem.php?id=2818
- Description
给定整数 N, 求 1<=x,y<=N 且 Gcd(x,y)为素数的数对 (x,y) 有多少对.
Input
一个整数 N
Output
如题
- Sample Input
- 4
- Sample Output
- 4
- HINT
对于样例(2,2),(2,4),(3,3),(4,2)
1<=N<=10^7
题解 Here!
啊, 好久没有看到过水题了...
题目要求:$Ans=\sum_{d\in prime}\sum_{i=1}^n\sum_{j=1}^n[gcd(i,j)==d]$
先保证 $n<=m$.
后面那玩意很明显来一发莫比乌斯反演啊...
不会?, 请看这道板子题: 洛谷 P3455 [POI2007]ZAP-Queries https://www.luogu.org/blog/49998/p3455-poi2007zap-queries
于是:$$Ans=\sum_{D=1}^n\lfloor\frac{n}{D}\rfloor\lfloor\frac{m}{D}\rfloor\sum_{d|D,d\in prime}\mu(\frac{D}{d})$$
前面的那玩意显然数论分块.
后面的那个枚举 $d\in prime$, 每个 $d$ 暴力算到它的倍数里去.
注: 这题卡空间, 不要开 $long\ long$...
附代码:
- #include<iostream>
- #include<algorithm>
- #include<cstdio>
- #define MAXN 10000010
- using namespace std;
- int n;
- int k=0,prime[MAXN],mu[MAXN],sum[MAXN];
- bool np[MAXN];
- inline int read(){
- int date=0,w=1;char c=0;
- while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
- while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
- return date*w;
- }
- void make(){
- int m=n;
- mu[1]=1;
- for(int i=2;i<=m;i++){
- if(!np[i]){
- prime[++k]=i;
- mu[i]=-1;
- }
- for(int j=1;j<=k&&prime[j]*i<=m;j++){
- np[prime[j]*i]=true;
- if(i%prime[j]==0)break;
- mu[prime[j]*i]=-mu[i];
- }
- }
- for(int i=1;i<=k;i++)
- for(int j=1;prime[i]*j<=m;j++)
- sum[prime[i]*j]+=mu[j];
- for(int i=1;i<=m;i++)sum[i]+=sum[i-1];
- }
- long long solve(int n,int m){
- long long ans=0;
- if(n>m)swap(n,m);
- for(int i=1,last=1;i<=n;i=last+1){
- last=min(n/(n/i),m/(m/i));
- ans+=(long long)(sum[last]-sum[i-1])*(n/i)*(m/i);
- }
- return ans;
- }
- int main(){
- n=read();
- make();
- printf("%lld\n",solve(n,n));
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2723661.html