POJ - 3090 Visible Lattice Points

分 析 这 道 题 目 , 我 们 发 现 除 了 ( 1 , 0 ) , ( 0 , 1 ) , ( 1 , 1 ) 三 个 钉 子 , 其 他 钉 子 被 看 到 , 只 有 满 足 了 分析这道题目,我们发现除了(1,0),(0,1),(1,1)三个钉子,其他钉子被看到,只有满足了 分析这道题目,我们发现除了(1,0),(0,1),(1,1)三个钉子,其他钉子被看到,只有满足了
1 ≤ x , y ≤ N , x ≠ y 1 ≤ x , y ≤ N , x ≠ y 而 且 g c d ( x , y ) = 1 1≤x,y≤N,x≠y1≤x,y≤N,x≠y 而且gcd(x,y)=1 1≤x,y≤N,x​=y1≤x,y≤N,x​=y而且gcd(x,y)=1

然 后 我 们 再 次 发 现 , 能 够 看 到 的 钉 子 , 是 沿 着 然后我们再次发现,能够看到的钉子,是沿着 然后我们再次发现,能够看到的钉子,是沿着(0,0)(n,n) 这 条 直 线 对 称 的 , 所 以 我 们 只 要 考 虑 其 中 一 半 就 好 了 , 然 后 最 后 乘 以 2 即 可 . 这条直线对称的,所以我们只要考虑其中一半就好了,然后最后乘以2即可. 这条直线对称的,所以我们只要考虑其中一半就好了,然后最后乘以2即可.

然 后 满 足 上 述 性 质 的 钉 子 , x 的 数 量 恰 好 就 是 φ ( y ) 然后满足上述性质的钉子,x的数量恰好就是φ(y) 然后满足上述性质的钉子,x的数量恰好就是φ(y)
有 了 性 质 的 数 学 题 目 是 什 么 , 就 是 直 接 套 公 式 ∑ i = 2 N φ ( i ) 有了性质的数学题目是什么,就是直接套公式\sum_{i=2}^{N}φ(i) 有了性质的数学题目是什么,就是直接套公式∑i=2N​φ(i)
利 用 E r a t o s h e n e s 筛 法 ， 利用Eratoshenes筛法， 利用Eratoshenes筛法， 我 们 可 以 在 O （ N l o g N ） 的 时 间 内 求 出 2   N 中 每 个 数 的 欧 拉 函 数 我们可以在O（NlogN）的时间内求出2~N中每个数的欧拉函数 我们可以在O（NlogN）的时间内求出2 N中每个数的欧拉函数

#include<iostream>
using namespace std;

typedef long long LL;
const int N = 1010;
int phi[N];

void get_eulers(int n)
{
	for(int i=2;i<=n;i++) phi[i]=i;
	for(int i=2;i<=n;i++)
		if(phi[i]==i)
			for(int j=i;j<=n;j+=i)
				phi[j]=phi[j]/i*(i-1);
}

int main()
{
	get_eulers(N-1);
	
	int T,n;
	cin>>T;
	for(int t=1;t<=T;t++)
	{
		cin>>n;
		int res=3;
		for(int i=2;i<=n;i++) res+=phi[i]*2;
		cout<<T<<" "<<n<<" "<<res<<endl; 
	}
	return 0;
}