Visible Lattice Points POJ - 3090(欧拉函数法雷序列)

我不是女神ヾ 2023-08-17 15:41 440阅读 0赞

# Visible Lattice Points POJ - 3090 #

题目链接：[https://vjudge.net/problem/POJ-3090\#author=lanti][https_vjudge.net_problem_POJ-3090_author_lanti]

## 题目： ##

![1705372-20190809235411131-1872448861.png][]

输入n，问从坐标(0,0)点能看到多少点，点的坐标范围是0<=(x,y)<=n  
只有一个点没有被另一个点挡住才能看到。  
如上图，n=5的时候，能看到21个点

第一行输入t，表示样例个数。1<=t<=1000 接下来t行，每行输入一个正整数n 。 1<=n<=1000Output输出n行三列。 第一列从1到n表示第i个样例，第二列输出n，第三列输出能看到的点的个数Sample Input

4
    2
    4
    5
    231

Sample Output

1 2 5
    2 4 13
    3 5 21
    4 231 32549
    
    思路：这道题想到斜率其实就很好办了，比如坐标为（1,2），（2,4），（3,6）在同一条直线上，所以就看做一个点，
    只要当后面坐标y/x可以再约分时，即gcd(x,y)!=1，那么其实这点的斜率之前已经有了
    不再考虑，当斜率为1,0，和不存在时分别仅有一个点，故一开始可先为3，然后再求一半三角区域的点数，
    3+该点数*2即为答案，区域的点数就是1~n与n互质的个数，即欧拉值，打表求出欧拉值后初始值为3。
    之后前一个值加上当前欧拉值*2即可。
    例如，n=4时，一半三角区域内部不包括三角边界时，3/4,2/4,1/4，求斜率分子与4互质个数即可（即欧拉值了），最后再乘以 2，再加上边界处的三条线的三个点即可。 所有斜率组成的序列跟法雷序列类似，
    法雷序列：对任意给定的一个自然数 n,将分母小于 n 的不可约的真分数按上升的次序排列,并且在第 一个分数前加上数 0/1,而在最后一个分数后加上数 1/1,这个序列被称为 n 级法雷序列

//
    // Created by hanyu on 2019/8/9.
    //
    #include <algorithm>
    #include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <queue>
    #include <set>
    #include<math.h>
    #include<map>
    using namespace std;
    typedef long long ll;
    const int maxn=3e6+7;
    #define MAX 0x3f3f3f3f
    int euler[maxn];
    void value()
    {
        memset(euler,0,sizeof(euler));
        euler[1]=1;
        for(int i=2;i<=maxn;i++)
        {
            if(!euler[i])
            {
                for(int j=i;j<=maxn;j+=i)
                {
                    if(!euler[j])
                        euler[j]=j;
                    euler[j]=euler[j]/i*(i-1);
                }
            }
        }
        euler[1]=3;
        for(int i=2;i<=maxn;i++)
            euler[i]=euler[i-1]+euler[i]*2;
    }
    int main()
    {
        int T,casee=0;
        value();
        scanf("%d",&T);
        while(T--)
        {
            int n;
            scanf("%d",&n);
            printf("%d %d %d\n",++casee,n,euler[n]);
        }
        return 0;
    }

# #

转载于:https://www.cnblogs.com/Vampire6/p/11330176.html

[https_vjudge.net_problem_POJ-3090_author_lanti]: https://vjudge.net/problem/POJ-3090#author=lanti
[1705372-20190809235411131-1872448861.png]: /images/20230810/61d9483b121a436dbf958556e6f97a71.png