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_{din prime}sum_{i=1}^nsum_{j=1}^n[gcd(i,j)==d]$
先保证$n<=m$。
后面那玩意很明显来一发莫比乌斯反演啊。。。
不会？，请看这道板子题：洛谷P3455 [POI2007]ZAP-Queries
于是：$$Ans=sum_{D=1}^nlfloorfrac{n}{D}
floorlfloorfrac{m}{D}
floorsum_{d|D,din prime}mu(frac{D}{d})$$
前面的那玩意显然数论分块。
后面的那个枚举$din 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
",solve(n,n));
return 0;
}