Visible Lattice Points poj3090

红太狼 2021-10-29 22:04 156阅读 0赞

[![知识共享许可协议][80x15.png]][80x15.png 1]  
本作品采用[知识共享署名-相同方式共享 4.0 国际许可协议][80x15.png 1]进行许可。  
题目链接：https://www.acwing.com/problem/content/203/  
在一个平面直角坐标系的第一象限内，如果一个点(x,y)与原点（0,0）的连线中没有通过其他任何点，则称该点在原点处是可见的。

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

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

![3090\_1.png][3090_1.png]

编写一个程序，计算给定整数N的情况下，满足0≤x，y≤N

的可见点（x，y）的数量（可见点不包括原点）。  
输入格式

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

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

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

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

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

1≤N,C≤1000

输入样例：

4  
2  
4  
5  
231

输出样例：

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

分析：  
这个题目意思很明确。  
我们观察图片可以知道（1，0） （1，1） （0，1）是必选的三个点。  
我们可以把其他点的坐标都写在一张纸上，不一会，你就会发现，这些点的坐标都满足一个条件： 即gcd（x，y） == 1.  
至此，我们就已经清楚，我们这个题目要求的是什么了。  
即，x，y互质的个数。在观察图片，  
我们发现，其实可以把图片分成两个部分，即以x=y这条直线，把这个图片分成上一部分和下一部分。我们可以发现这两个部分个数是相等的。  
目前，我们的目的转化为：  
1<=x<= y 在这个范围内 找到与y互质的个数。  
很明显，这是个欧拉函数。

#include"stdio.h"
    #include"string.h"
    #include"algorithm"
    using namespace std;
    typedef long long ll;
    
    int T,n;
    
    ll Ola(int n)
    {
        ll cnt = n;
        for(int i = 2; i <= n;i ++)
        {
            if(n % i) continue;
            cnt = cnt / i * (i - 1);
            while(n % i == 0)
            {
                n = n / i;
            }
        }
        if(n != 1) cnt = cnt / n * (n - 1);
        return cnt;
    }
    int main()
    {
        int cnt = 1;
        scanf("%d",&T);
        while(T --)
        {
            scanf("%d",&n);
            int m = n;
            ll cont = 0;
            for(int i = 2; i <= n;i ++)
              cont += Ola(i);
            printf("%d %d %lld\n",cnt ++,m,2 * cont + 3);
        }
    }

[80x15.png]: https://i.creativecommons.org/l/by-sa/4.0/80x15.png
[80x15.png 1]: http://creativecommons.org/licenses/by-sa/4.0/
[3090_1.png]: /images/20211029/835548a152324cc7b981f9c76d40fa02.png