首页 > 代码库 > POJ 3090 (欧拉函数) Visible Lattice Points
POJ 3090 (欧拉函数) Visible Lattice Points
题意：
UVa 10820
这两个题是同一道题目，只是公式有点区别。
给出范围为(0, 0)到(n, n)的整点，你站在原点处，问有多少个整点可见。
对于点(x, y), 若g = gcd(x, y) > 1，则该点必被点(x/g, y/g)所挡住。
因此所见点除了(1, 0)和(0, 1)满足横纵坐标互素。
最终答案为
,其中的+3对应(1, 1) (1, 0) (0, 1)三个点
1 #include <cstdio> 2 3 const int maxn = 1000; 4 int phi[maxn + 10]; 5 6 void get_table() 7 { 8 for(int i = 2; i <= maxn; ++i) if(!phi[i]) 9 {10 for(int j = i; j <= maxn; j += i)11 {12 if(!phi[j]) phi[j] = j;13 phi[j] = phi[j] / i * (i - 1);14 }15 }16 }17 18 int main()19 {20 freopen("3090in.txt", "r", stdin);21 22 get_table();23 for(int i = 1; i <= maxn; ++i) phi[i] += phi[i - 1];24 25 int T;26 scanf("%d", &T);27 for(int kase = 1; kase <= T; ++kase)28 {29 int n;30 scanf("%d", &n);31 printf("%d %d %d\n", kase, n, phi[n]*2+3);32 }33 34 return 0;35 }
POJ 3090 (欧拉函数) Visible Lattice Points
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。