boj 2725 : Visible Lattice Points

boj 2725 : Visible Lattice Points

https://www.acmicpc.net/problem/2725

(0,1),(1,0)을 제외한다면 (x,y)가 보인다는 것은 gcd(x,y) 가 1이라는 것이다.

이를이용하여 for문 2개로 문제를 해결할 수 있다.




for (int i = 2; i <= 1000; i++) {

int cnt = 0;

for (int j = 1; j < i; j++) {

cnt += (gcd(i, j) == 1);

}

b[i] = b[i - 1] + 2 * cnt;

}

그런데, 다른사람들의 코드를 보니 더 위의 n*n*logn의 복잡도보다 더 간단하게 n*sqrt(n)으로도 해결할 수 있었다..^^;

n과 서로소인 n보다 작은 수를 구하는 오일러 피 공식을 이용하면 된다.

이 경우 시간복잡도는 n*sqrt(n)