3090:Visible Lattice Points

keyword

有理数　格子点　C++

概要

原点から[0,n]*[0,n](n<1000)の各格子点に対して直線が何本引けるか求める問題。
有理数ライブラリから引っ張ってきてsetに突っ込んでも良さそうだけど、x座標とy座標が互いに素であるものだけをカウントすれば良い。

int main(){
    int ans[1010];
    int i, j, n, rept, cnt;
    REP(i,1010) ans[i] = 0;

    ans[1] = 3;
    for(i=2; i<=1000; i++){
        cnt = 0;
        for(j=1;j<i;j++)if(__gcd(i,j)==1)cnt++;
        ans[i] = ans[i-1] + cnt*2;
    }

    scanf("%d",&rept);
    LOOP(rept){
        scanf("%d",&n);
        printf("%d %d %d\n",loopCount, n, ans[n]);
    }

    return 0;
}