PKU : 3090 - Visible Lattice Points

実装問題

問題概要

http://poj.org/problem?id=3090

0 <= x,y <= N の範囲で, 格子点が(0,0)からいくつ見えるかを答えよ.

アルゴリズム

全格子点が見えるか見えないかを, 最初に全て列挙してしまう.
(三重ループ or XとYが互いに素な点を探す)
さらに, 答えの値もそのときに求めておく.
あとは, Nが入力されたら出力するだけ.

プログラム

bool flg[1002][1002];
int cnt[1002];
int ans[1002];

int main(void){
  memset(flg,true,sizeof(flg));
  memset(cnt,0,sizeof(cnt));
  flg[0][0] = false;
  rep(i,1001){
    rep(j,1001){
      if(!flg[i][j]) continue;
      cnt[max(i,j)]++;

      int x = j + j;
      int y = i + i;
      while(x <= 1000 && y <= 1000){
        flg[y][x] = false;
        x += j;
        y += i;
      }
    }
  }

  REP(i,1,1001){
    ans[i] = ans[i-1] + cnt[i];
  }

  int T;
  scanf("%d",&T);

  rep(i,T){
    int n;
    scanf("%d",&n);
    printf("%d %d %d\n",i+1,n,ans[n]);
  }
}