不同于题201,不是求互质对的数,而是求x,y
最大公约数gcd(x,y)
是素数的对数
$gcd(x,y)=p \iff gcd(\frac{x}{p},\frac{y}{p})=1$
$统计 gcd(x,y)=p \in [0,N]对数\iff 统计gcd(\frac{x}{p},\frac{y}{p})=1 \in[0,\frac{N}{p}]对数$
$\iff x’,y’\in[0,\frac{N}{p}]互质数的对数$
问题转化为题201,只不过$N$变成了$\frac{N}{p}$
最后即求$\phi[i]前缀和×2 + 1$
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 1e7 + 10;
int primes[N], cnt;
bool st[N];
int phi[N];
LL s[N];
void init(int n)
{
for(int i=2;i<=n;i++)
{
if(!st[i])
{
primes[cnt++]=i;
phi[i] = i-1;
}
for(int j =0;primes[j]*i<=n;j++)
{
st[primes[j]*i]=true;
if(i%primes[j]==0)
{
phi[i*primes[j]] = phi[i]*primes[j];
break;
}
phi[i*primes[j]] = phi[i]*(primes[j]-1);
}
}
for(int i =1;i<=n;i++)s[i]=s[i-1]+phi[i];
}
int main()
{
int n;
cin >> n;
init(n);
LL res = 0;
for(int i=0;i<cnt;i++)
{
int p=primes[i];
res+=s[n/p]*2+1;
}
cout << res << endl;
return 0;
}
为啥需要加1?
y=x上面还有一个点
因为我们算的是,对于每一个 <= n 的p,n / p = 1的话意味着1 - n中包含一个数p,而gcd(p,p) = p,也满足题意,而且p = p,不应该被*2计算,所以 + 1
换句话说,对于每一个p,gcd(p,p) = p,也是一个点,需要被计算一次
也就是说,在y =x 这条线上,所有y = p,x = p的点都算作内
stO Orz
Orz
为啥phi[1]=0呢
y=x那条直线上的最后才算,也就是(1,1)
后来想通了 %%%%%%%%%%%%%%%%%%%%%%
应该是起点是1,1吧,