POJ 3090-Visible Lattice Points

[mathjax]
题目链接:POJ 3090

题意:
在\((0,0)\)为左下角,\((N,N)\)为右上角的矩形中,除了\((0,0)\)之外,每个点上都插着一个钉子,如下图所示.求在\((0,0)\)往四周看,能够看多少个钉子.一个钉子能被看到,当且仅当连接它和原点的线段上没有其他钉子.

Solution:
除了\((1,0),(0,1),(1,1)\)这三个钉子外,一个钉子\((x,y)\)能被看到当且仅当\(gcd(x,y)=1\),即互质.并且观察可以发现,能看到的钉子关于\(y=x\)对称.于是可以只考虑一半,转化为求对于每个\(2<=x<=N\),有多少个y满足\(1<=y<x\)且\(gcd(x,y)=1\),即x的欧拉函数值. 可以通过Eratosthenes筛法求出\([2,y]\)中每个数的欧拉函数,也可以用线性筛法.

code:

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <string>

using namespace std;
#define MAX_N 2000000001

typedef long long ll;
typedef unsigned long long ull;

int phi[1005];

void euler(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() {
  int T;
  cin>>T;
  euler(1000);
  int kase=0;
  while(T--){
    int n;
    cin>>n;
    int ans=3;
    for(int i=2;i<=n;i++){
      ans+=phi[i]*2;
    }
    printf("%d %d %d\n",++kase,n,ans);
  }
  return 0;
}