先来看一下题意
本题的本质是，输入 $n$ ，有多少个二元组$(x,y)$满足$gcd(x,y)=1$
而我们不难想到
对于某个 $x$ ，小于 $x$ 的与它互质的数的个数就是$phi(x)$，因为$x$和$y$交换算两次，所以是$2×phi(x)$。
对于$(1,1)$是不能交换的。
所以就是
所以输入 $n$ ，答案就是$1+2*\sum{_{i=2}^n phi(i)}$,输出即可。
先看一下求 $Euler$
我们可以用一个$euler$函数也就是$euler$线性筛法：$EulerTable()$，$phi[x]$用来计算 $x$ 的个数的euler值（如果不会$euler$的小伙伴，你应该先自学一下$euler$）。
ll phi[1900900],prime[1900900],tot;
void EulerTable(ll n)
{
phi[1]=1;
for(ll i=2;i<=n;i++)
{
if(phi[i]==0)
{
phi[i]=i-1,prime[tot++]=i;
}
for(ll j=0;j<tot && i*prime[j]<=n;j++)
{
if(i%prime[j]==0)
{
phi[i*prime[j]]=phi[i]*prime[j];
break;
}
else
{
phi[i*prime[j]]=phi[i]* (prime[j]-1);
}
}
}
}最后
我们看看主函数。
先计算一下到 50011 的所有数的Euler值，调一遍EulerTable函数即可。
然后跟据上面的思路可以写出
int main(){
EulerTable(50011);
ll n;
scanf("%lld",&n);
while(n!=0)
{
ll ans=0;
for(int i=2;i<=n;i++)
{
ans+=phi[i];
}
printf("%lld\n",ans<<1|1);
scanf("%lld",&n);
}
}最后附上完整代码
$\color{red}Code:$
#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;
const ll MAXN=50011;
ll phi[1900900],prime[1900900],tot;
void EulerTable(ll n)
{
phi[1]=1;
for(ll i=2;i<=n;i++)
{
if(phi[i]==0)
{
phi[i]=i-1,prime[tot++]=i;
}
for(ll j=0;j<tot && i*prime[j]<=n;j++)
{
if(i%prime[j]==0)
{
phi[i*prime[j]]=phi[i]*prime[j];
break;
}
else
{
phi[i*prime[j]]=phi[i]* (prime[j]-1);
}
}
}
}
int main(){
EulerTable(50011);
ll n;
scanf("%lld",&n);
while(n!=0)
{
ll ans=0;
for(int i=2;i<=n;i++)
{
ans+=phi[i];
}
printf("%lld\n",ans<<1|1);
scanf("%lld",&n);
}
}