UVA10820 交表 Send a Table

\(\Large\textbf{Description:} \large{输入n，求有多少个二元组(x,y)满足：1\leqslant x,y\leqslant n，且x和y互素。}\)

\(\Large\textbf{Solution:} \large{不难发现除了(1,1)外，其他二元组的x，y都不相等。设满足x < y的二元组有g(n)个，那么答案为2\times g(n) + 1。}\)

\(\Large\textbf{Code:}\)

#include<bits/stdc++.h>
using namespace std;
int ph[50010];
int n,m;
void phi(int n)
{
    for(int i=2;i<=n;i++)ph[i]=0;
    ph[1]=1;
    for(int i=2;i<=n;i++)
    if(!ph[i])
    {
        for(int j=i;j<=n;j+=i)
        {
         if(!ph[j]) ph[j]=j;
         ph[j]=ph[j]/i*(i-1);   
        }
    }
}
int main()
{
    while(scanf("%d",&n)&&n!=0)
    {
    phi(n);
    int ans=0;
    for(int i=2;i<=n;i++)
     ans+=ph[i];
    cout<<2*ans+1<<endl;
    }
    return 0;
}

\(\large\color{pink}{by\quad Miraclys}\)

UVA10820 交表 Send a Table

原文：https://www.cnblogs.com/Miraclys/p/12263849.html