poj3090 Visible Lattice Points

答案就是 (3+2 imes sum_{i=2}^n varphi(i))，记得特判

#include <iostream>
#include <cstdio>
using namespace std;
int n, T, phi[1005];
void shai(){
	for(int i=1; i<=1000; i++)
		phi[i] = i;
	for(int i=2; i<=1000; i++)
		if(phi[i]==i)
			for(int j=i; j<=1000; j+=i)
				phi[j] = phi[j] / i * (i - 1);
}
int main(){
	shai();
	for(int i=3; i<=1000; i++)
		phi[i] += phi[i-1];
	cin>>T;
	for(int i=1; i<=T; i++){
		scanf("%d", &n);
		if(n==1){
			printf("%d %d 3
", i, n);
			continue;
		}
		printf("%d %d %d
", i, n, 3+2*phi[n]);
	}
	return 0;
}