欧拉函数 - Visible Lattice Points - POJ 3090

在一个平面直角坐标系的第一象限内，如果一个点(x,y)与原点（0,0）的连线中没有通过其他任何点，则称该点在原点处是可见的。

例如，点(4,2)就是不可见的，因为它与原点的连线会通过点(2,1)。

部分可见点与原点的连线如下图所示：

编写一个程序，计算给定整数N的情况下，满足0≤x，y≤N的可见点（x，y）的数量（可见点不包括原点）。

输入格式

第一行包含整数C，表示共有C组测试数据。

每组测试数据占一行，包含一个整数N。

输出格式

每组测试数据的输出占据一行。

应包括：测试数据的编号（从1开始），该组测试数据对应的N以及可见点的数量。

同行数据之间用空格隔开。

数据范围

$1\le N,C\le 1000$

输入样例：

4
2
4
5
231

输出样例：

1 2 5
2 4 13
3 5 21
4 231 32549

分析：

$\mathrm{在}\mathrm{点}\mathrm{阵}\mathrm{中}\mathrm{，}\mathrm{任}\mathrm{意}\mathrm{两}\mathrm{点}(x_1,y_1)\mathrm{、}(x_2,y_2)\mathrm{的}\mathrm{连}\mathrm{线}L\mathrm{，}L\mathrm{不}\mathrm{经}\mathrm{过}\mathrm{其}\mathrm{他}\mathrm{格}\mathrm{点}\mathrm{的}\mathrm{充}\mathrm{要}\mathrm{条}\mathrm{件}\mathrm{是}\mathrm{：}$

$\frac{y_2?y_1}{x_2?x_1}\mathrm{是}\mathrm{最}\mathrm{简}\mathrm{整}\mathrm{数}\mathrm{比}\mathrm{，}\mathrm{即}gcd(y_2?y_1,x_2?x_1)=1\mathrm{。}$

$\mathrm{很}\mathrm{好}\mathrm{理}\mathrm{解}\mathrm{。}\mathrm{因}\mathrm{为}\mathrm{，}\mathrm{假}\mathrm{设}\mathrm{存}\mathrm{在}{x}_2?x_1=2\mathrm{，}{y}_2?y_1=2\mathrm{，}\mathrm{如}\mathrm{下}\mathrm{图}$

$\mathrm{则}\mathrm{存}\mathrm{在}(x_3,y_3)\mathrm{，}\mathrm{使}\mathrm{得}{y}_3?y_1=\frac{1}{2}(y_2?y_1)\mathrm{，}{x}_3?x_1=\frac{1}{2}(x_2?x_1)$

本题：

$\mathrm{本}\mathrm{题}\mathrm{已}\mathrm{固}\mathrm{定}\mathrm{一}\mathrm{点}(0,0)\mathrm{，}\mathrm{问}\mathrm{题}\mathrm{即}\mathrm{求}\mathrm{点}\mathrm{对}(x,y)\mathrm{的}\mathrm{数}\mathrm{量}\mathrm{，}\mathrm{满}\mathrm{足}gcd(x,y)=1\mathrm{。}$

$\mathrm{由}\mathrm{于}\mathrm{图}\mathrm{关}\mathrm{于}y=x\mathrm{对}\mathrm{称}\mathrm{，}\mathrm{我}\mathrm{们}\mathrm{仅}\mathrm{需}\mathrm{计}\mathrm{算}\mathrm{一}\mathrm{半}\mathrm{再}\mathrm{乘}2\mathrm{即}\mathrm{可}\mathrm{。}$

$gcd(x,y)=1\mathrm{，}\mathrm{即}x\mathrm{与}y\mathrm{互}\mathrm{质}\mathrm{，}$

$\mathrm{我}\mathrm{们}\mathrm{从}\mathrm{横}\mathrm{坐}\mathrm{标}\mathrm{逐}\mathrm{个}\mathrm{递}\mathrm{增}\mathrm{统}\mathrm{计}\mathrm{，}\mathrm{就}\mathrm{是}\mathrm{对}\mathrm{每}\mathrm{一}\mathrm{个}x\mathrm{，}\mathrm{统}\mathrm{计}[1,x?1]\mathrm{中}\mathrm{，}\mathrm{与}x\mathrm{互}\mathrm{质}\mathrm{的}\mathrm{数}\mathrm{的}\mathrm{个}\mathrm{数}\mathrm{。}$

$\mathrm{这}\mathrm{就}\mathrm{将}\mathrm{问}\mathrm{题}\mathrm{转}\mathrm{化}\mathrm{为}\mathrm{求}\mathrm{欧}\mathrm{拉}\mathrm{函}\mathrm{数}\mathrm{。}$

$\mathrm{答}\mathrm{案}\mathrm{：}{\sum }_{i=1}^n?(i)\times 2.$

代码：

#include<iostream>

using namespace std;

const int N=1010;

int primes[N],cnt;
bool st[N];
int phi[N];

void get_prime(int n)
{
    for(int i=2;i<=n;i++)
    {
        phi[1]=1;
        if(!st[i]) 
        {
            phi[i]=i-1;
            primes[cnt++]=i;
        }
        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);
        }
    }
}

int main()
{
    get_prime(N-1);
    
    int n,m;
    cin>>m;
    for(int T=1;T<=m;T++)
    {
        cin>>n;
        int res=1;
        for(int i=1;i<=n;i++) res+=phi[i]*2;
        cout<<T<<' '<<n<<' '<<res<<endl;
    }
    return 0;
}