poj 3090 Visible Lattice Points(数论：筛法打表欧拉函数)

本文主要是介绍poj 3090 Visible Lattice Points(数论：筛法打表欧拉函数)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

和之前做过的一个题很像

对于size==4

从1到4考虑y坐标

不妨设x>=y

y==1: (1,1)

y==2: (1,2)

y==3: (1, 3) (2, 3)

y==4: (1, 4) (3, 4)

共6个满足条件，把x y交换下且去除(1, 1)的重复情况得到2×6-1=11

再加上(0,1) (1,0)两种情况得到13

所以结果应该为：

代码如下：

#include <cmath>
#include <cstdio>
using namespace std;int phi[1020];void phi_table(int n) {for(int i=2; i<=n; ++i)phi[i] = 0;phi[1] = 1;for(int i=2; i<=n; ++i) {if(!phi[i]) {for(int j=i; j<=n; j+=i) {if(!phi[j])phi[j] = j;phi[j] = phi[j]/i*(i-1);}}}for(int i=2; i<=n; ++i)phi[i] += phi[i-1];
}int main(void) {int T, n;phi_table(1010);scanf("%d", &T);for(int t=1; t<=T; ++t) {scanf("%d", &n);printf("%d %d %d\n", t, n, phi[n]*2+1);}return 0;
}

 

这篇关于poj 3090 Visible Lattice Points(数论：筛法打表欧拉函数)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---