Visible Lattice Points POJ - 3090
题目链接: https://vjudge.net/problem/POJ-3090#author=lanti
题目:
输入 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
- 2 5
- 4 13
- 5 21
- 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;
- }
来源: http://www.bubuko.com/infodetail-3150074.html