【题目链接】
http://www.lydsy.com/JudgeOnline/problem.php?id=2818
【题意】
问(x,y)为质数的有序点对的数目。
【思路一】
定义f[i]表示i之前(x,y)=1的有序点对的数目，则有递推式：
f[1]=1
f[i]=f[i-1]+phi[i]*2
我们依次枚举小于n的所有素数，对于素数t，(x,y)=t的数目等于(x/t,y/t)，即f[n/t]。
【代码一】
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std; typedef long long ll;
const int N = 1e7+; int su[N],tot,phi[N];
ll f[N]; void get_pre(int n)
{
phi[]=;
for(int i=;i<=n;i++) if(!phi[i]) {
su[++tot]=i;
for(int j=i;j<=n;j+=i) {
if(!phi[j]) phi[j]=j;
phi[j]=phi[j]/i*(i-);
}
}
f[]=;
for(int i=;i<=n;i++) f[i]=f[i-]+*phi[i];
} int n; int main()
{
scanf("%d",&n);
get_pre(n);
ll ans=;
for(int i=;i<=tot;i++)
ans+=f[n/su[i]];
printf("%lld\n",ans);
return ;
}
【思路二】
其它思路一样，不同的是使用莫比乌斯反演计算(x,y)=1的数目，累计答案的时间复杂度为O(n sqrt(n))
推倒过程：
【代码二】
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std; typedef long long ll;
const int N = 1e7+; int su[N],mu[N],tot,vis[N]; void get_mu(int n)
{
mu[]=;
for(int i=;i<=n;i++) {
if(!vis[i]) {
su[++tot]=i;
mu[i]=-;
}
for(int j=;j<=tot&&su[j]*i<=n;j++) {
vis[i*su[j]]=;
if(i%su[j]==) mu[i*su[j]]=;
else mu[i*su[j]]=-mu[i];
}
}
for(int i=;i<=n;i++) mu[i]+=mu[i-];
} int n; ll calc(int n)
{
int i,last; ll ans=;
for(int i=;i<=n;i=last+) {
last=n/(n/i);
ans+=(ll)(n/i)*(n/i)*(mu[last]-mu[i-]);
}
return ans;
} int main()
{
// freopen("in.in","r",stdin);
// freopen("out.out","w",stdout);
scanf("%d",&n);
get_mu(n);
ll ans=;
for(int i=;i<=tot;i++)
ans+=calc(n/su[i]);
printf("%lld\n",ans);
return ;
}
UPD.16/4/8
另外莫比乌斯反演还有一种O(n)预处理O(sqrt(n))查询的做法 click Here