boj 2725 : Visible Lattice Points

Problem Solving

boj 2725 : Visible Lattice Points

1ssrek 2016. 8. 26. 18:24

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보다 작은 수를 구하는 오일러 피 공식을 이용하면 된다.

$\varphi (p^{k})=p^{k}-p^{k-1}=p^{k-1}(p-1)=p^{k}\left(1-{\frac {1}{p}}\right).$

${\begin{aligned}\varphi (n)&=\varphi (p_{1}^{k_{1}})\varphi (p_{2}^{k_{2}})\cdots \varphi (p_{r}^{k_{r}})\\&=p_{1}^{k_{1}}\left(1-{\frac {1}{p_{1}}}\right)p_{2}^{k_{2}}\left(1-{\frac {1}{p_{2}}}\right)\cdots p_{r}^{k_{r}}\left(1-{\frac {1}{p_{r}}}\right)\\&=p_{1}^{k_{1}}p_{2}^{k_{2}}\cdots p_{r}^{k_{r}}\left(1-{\frac {1}{p_{1}}}\right)\left(1-{\frac {1}{p_{2}}}\right)\cdots \left(1-{\frac {1}{p_{r}}}\right)\\&=n\left(1-{\frac {1}{p_{1}}}\right)\left(1-{\frac {1}{p_{2}}}\right)\cdots \left(1-{\frac {1}{p_{r}}}\right).\end{aligned}}$

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

저작자표시 (새창열림)