欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

欧拉函数 - Visible Lattice Points - POJ 3090

程序员文章站 2022-03-27 21:19:12
欧拉函数 - Visible Lattice Points - POJ 3090在一个平面直角坐标系的第一象限内,如果一个点(x,y)与原点(0,0)的连线中没有通过其他任何点,则称该点在原点处是可见的。例如,点(4,2)就是不可见的,因为它与原点的连线会通过点(2,1)。部分可见点与原点的连线如下图所示:编写一个程序,计算给定整数N的情况下,满足0≤x,y≤N的可见点(x,y)的数量(可见点不包括原点)。输入格式第一行包含整数C,表示共有C组测试数据。每组测试数据占一行,包含一个整数N。...

欧拉函数 - Visible Lattice Points - POJ 3090

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

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

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

欧拉函数 - Visible Lattice Points -  POJ 3090

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

输入格式

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

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

输出格式

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

应包括:测试数据的编号(从1开始),该组测试数据对应的N以及可见点的数量。

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

数据范围

1N,C10001≤N,C≤1000

输入样例:

4
2
4
5
231

输出样例:

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

分析:

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

y2y1x2x1gcd(y2y1,x2x1)=1\frac{y_2-y_1}{x_2-x_1}是最简整数比,即gcd(y_2-y_1,x_2-x_1)=1。

x2x1=2y2y1=2很好理解。因为,假设存在x_2-x_1=2,y_2-y_1=2,如下图

欧拉函数 - Visible Lattice Points -  POJ 3090

(x3,y3)使y3y1=12(y2y1)x3x1=12(x2x1)则存在(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)

本题:

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

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

gcd(x,y)=1xygcd(x,y)=1,即x与y互质,

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

这就将问题转化为求欧拉函数。
欧拉函数 - Visible Lattice Points -  POJ 3090
i=1nϕ(i)×2.答案:\sum_{i=1}^n\phi(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