链接:
题意:
在一个平面直角坐标系的第一象限内, 如果一个点 (x,y) 与原点 (0,0) 的连线中没有通过其他任何点, 则称该点在原点处是可见的.
例如, 点 (4,2) 就是不可见的, 因为它与原点的连线会通过点(2,1).
部分可见点与原点的连线如下图所示:
编写一个程序, 计算给定整数 N 的情况下, 满足 0≤x,y≤N 的可见点 (x,y) 的数量(可见点不包括原点).
思路:
考虑当 gcd(x, y) != 1 时, 坐标 (x/gcd(x, y), y/gcd(x, y)) 和坐标(x, y), 位于一条直线上.
所以只有 gcd(x, y)为 1 的点可以看得到. 打个表, 再在答案上加 1 即可. 考虑(1, 1)
代码:
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long LL;
- LL Cnt[1010];
- int n;
- int Euler(int x)
- {
- int res = x;
- for (int i = 2;i <= x;i++)
- {
- if (x%i == 0)
- {
- while (x % i == 0)
- x /= i;
- res = res/i*(i - 1);
- }
- }
- if (x> 1)
- res = res/x*(x-1);
- return res;
- }
- int main()
- {
- for (int i = 1;i <= 1000;i++)
- Cnt[i] = Cnt[i-1]+Euler(i)*2;
- int t, cnt = 0;
- scanf("%d", &t);
- while (t--)
- {
- scanf("%d", &n);
- printf("%d %d %lld\n", ++cnt, n, Cnt[n]+1);
- }
- return 0;
- }
Acwing-201 - 可见的点(数学, 欧拉函数)
来源: http://www.bubuko.com/infodetail-3210149.html