欧拉函数 – 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 ≤ N , C ≤ 1000 1≤N,C≤1000 1≤N,C≤1000

输入样例：

输出样例：

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

分析：

在点阵中，任意两点 ( x 1 , y 1 ) 、 ( x 2 , y 2 ) 的连线 L ， L 不经过其他格点的充要条件是：在点阵中，任意两点(x_1,y_1)、(x_2,y_2)的连线L，L不经过其他格点的充要条件是：在点阵中，任意两点(x1,y1)、(x2,y2)的连线L，L不经过其他格点的充要条件是：

y 2 − y 1 x 2 − x 1 是最简整数比，即 g c d ( y 2 − y 1 , x 2 − x 1 ) = 1 。 \frac{y_2-y_1}{x_2-x_1}是最简整数比，即gcd(y_2-y_1,x_2-x_1)=1。 x2−x1y2−y1是最简整数比，即gcd(y2−y1,x2−x1)=1。

很好理解。因为，假设存在 x 2 − x 1 = 2 ， y 2 − y 1 = 2 ，如下图很好理解。因为，假设存在x_2-x_1=2，y_2-y_1=2，如下图很好理解。因为，假设存在x2−x1=2，y2−y1=2，如下图

则存在 ( x 3 , y 3 ) ，使得 y 3 − y 1 = 1 2 ( y 2 − y 1 ) ， x 3 − x 1 = 1 2 ( x 2 − x 1 ) 则存在(x_3,y_3)，使得y_3-y_1=\frac{1}{2}(y_2-y_1)，x_3-x_1=\frac{1}{2}(x_2-x_1) 则存在(x3,y3)，使得y3−y1=21(y2−y1)，x3−x1=21(x2−x1)

本题：

本题已固定一点 ( 0 , 0 ) ，问题即求点对 ( x , y ) 的数量，满足 g c d ( x , y ) = 1 。本题已固定一点(0,0)，问题即求点对(x,y)的数量，满足gcd(x,y)=1。本题已固定一点(0,0)，问题即求点对(x,y)的数量，满足gcd(x,y)=1。

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

g c d ( x , y ) = 1 ，即 x 与 y 互质， gcd(x,y)=1，即x与y互质， gcd(x,y)=1，即x与y互质，

我们从横坐标逐个递增统计，就是对每一个 x ，统计 [ 1 , x − 1 ] 中，与 x 互质的数的个数。我们从横坐标逐个递增统计，就是对每一个x，统计[1,x-1]中，与x互质的数的个数。我们从横坐标逐个递增统计，就是对每一个x，统计[1,x−1]中，与x互质的数的个数。

这就将问题转化为求欧拉函数。这就将问题转化为求欧拉函数。这就将问题转化为求欧拉函数。

答案： ∑ i = 1 n ϕ ( i ) × 2. 答案：\sum_{i=1}^n\phi(i)×2. 答案：∑i=1nϕ(i)×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;
}

本文地址：https://blog.csdn.net/njuptACMcxk/article/details/107343621

黄山市民网：https://www.huangshanshimin.com/

欧拉函数 – Visible Lattice Points – POJ 3090

相关文章