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


'Problem Solving > Algorithm notes' 카테고리의 다른 글

Euler's phi (Totient function)  (0) 2016.08.15
Inversion Count  (0) 2016.01.31
The Tower of Hanoi  (0) 2011.08.28
점과 선분과의 거리  (2) 2011.01.22
Konig's Theorem  (0) 2010.08.01
Modular Multiplicative Inverse  (0) 2010.06.13
Primality Testing (Miller-Rabin)  (0) 2010.03.23
Modular Exponentiation (Big Mod)  (2) 2010.02.19
KMP (Knuth-Morris-Pratt) Algorithm  (0) 2009.11.15
Bell Number  (0) 2009.07.12

to Top