Gaussian Prime
Problem Solving/Algorithm notes 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
'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 |