Problem Solving/Algorithm notes
Gaussian Prime
helloneo
2011. 4. 3. 22:03
LA 3196 - Gaussian Prime Factors 를 결국 풀어냈다..
06년도 마닐라 대회를 출전했다가.. 저 문제에서 말렸던 기억이 나는데..
문제 description 도 너무 이상하고.. 그때는 도대체 무슨말인지 이해를 못했었다..
최근에 Gaussian Prime 자료를 찾아보고 나서야 문제가 뭐를 묻는지 이해할 수 있었다..
a + bi (여기서 i = sqrt(-1)) 가 prime 이 되는 조건은
1) |a|, |b| > 0 일때, a^2 + b^2 = prime 인 경우
2) b = 0 일때, |a| = prime 이고 |a| mod 4 = 3 인 경우
3) a = 0 일때, |b| = prime 이고 |b| mod 4 = 3 인 경우
참고: Gaussian Prime
06년도 마닐라 대회를 출전했다가.. 저 문제에서 말렸던 기억이 나는데..
문제 description 도 너무 이상하고.. 그때는 도대체 무슨말인지 이해를 못했었다..
최근에 Gaussian Prime 자료를 찾아보고 나서야 문제가 뭐를 묻는지 이해할 수 있었다..
a + bi (여기서 i = sqrt(-1)) 가 prime 이 되는 조건은
1) |a|, |b| > 0 일때, a^2 + b^2 = prime 인 경우
2) b = 0 일때, |a| = prime 이고 |a| mod 4 = 3 인 경우
3) a = 0 일때, |b| = prime 이고 |b| mod 4 = 3 인 경우
참고: Gaussian Prime