题解 - [POJ 3361] Gaussian Prime Factors

发表于 更新于 分类于 ， 本文字数： 501 阅读时长 ≈ 2 分钟

题目链接

原始题面

Description

Let \(a, b, c, d\) be integers. The complex number \(a+bj\), where \(j^2 = -1\), is a factor of \(c+dj\), if there exist integers \(e\) and \(f\) such that

\(c + dj = (a + bj)(e + fj)\)

A complex number \(a + bj\) where \(a\) and \(b\) are integers is a Gaussian prime if the factors are \(1, -1, -a - bj\) and \(a + bj\) only

The following are Gaussian primes: \(1 + j, 1 - j, 1 + 2j, 1 - 2j, 3\) and \(7\)

The Gaussian prime factors of 5 are:

\(1 + 2j\) and \(1 - 2j\), or
\(2 + j\) and \(2 - j\), or
\(-1 - 2j\) and \(-1 + 2j\), or
\(-2 - j\) and \(-2 + j\)

Write a program that finds all the Gaussian prime factors of a positive integer

Input

One line of input per case. The line represents a positive integer \(n\)

Output

One line of output per test case. The line represents the Gaussian prime factors of \(n\). If \(a + bj\) is a Gaussian prime factor of \(n\), then \(a > 0\), \(|b| ≥ a\), if \(b ≠ 0\). If \(b = 0\), the output must be \(a\)

Sample Input

1
2
3
4
2
5
6
700

Sample Output

1
2
3
4
Case #1: 1+j, 1-j
Case #2: 1+2j, 1-2j
Case #3: 1+j, 1-j, 3
Case #4: 1+j, 1-j, 1+2j, 1-2j, 7

Hint

Output the Gaussian prime factors in ascending order of \(a\). If there are more than one factors with the same \(a\), output them in ascending order of \(b\) by absolute value. If two conjugate factors coexist, the one with a positive imaginary part precedes that with a negative imaginary part

Source

Manila 2006

题意简述

给出整数 \(s\), 输出在 \(\mathbb{Z}[j]\) 下的所有非平凡素因子，其中 \(j^2=-1\)

解题思路

题面的 Hint 里提到了做法，这里简要概括一下

  • 首先对 \(s\) 做质因数分解
  • 其次考察 \(s\) 的每个质因子 \(p\)
    • 若 \(p\equiv 3\pmod4\), 说明 \(p\) 不能表示成二平方和的形式，故 \(p\) 也是 \(\mathbb{Z}[j]\) 下的素数 (即 Gauss 素数)
    • 若 \(p\equiv 1\pmod4\), 说明 \(p\) 能表示成二平方和的形式，设 \(p=a^2+b^2\) 则 \(a+bi,~a-bi\) 是 Gauss 素数而 \(p\) 不是

最后输出结果的时候要按 \(a\) 升序输出，如果对于相同的 \(a\), 有多个对应的 \(b\ne0\), 则按 \(b\) 升序输出一组共轭的 Gauss 素数

代码参考

Show code

POJ_3361view raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
/*
 * @Author: Tifa
 * @Description: From <https://github.com/Tiphereth-A/CP-archives>
 * !!! ATTENEION: All the context below is licensed under a 
 *  GNU Affero General Public License, Version 3.
 *  See <https://www.gnu.org/licenses/agpl-3.0.txt>.
 */
#include <cmath>
#include <cstdio>
#include <queue>
using std::priority_queue;
struct Complex {
  int re, im;
  Complex(int a = 0, int b = 0): re(a), im(b) {}
  bool operator<(const Complex &rhs) const {
    return re == rhs.re ? im > rhs.im : re > rhs.re;
  }
};
int main() {
  int n, kase = 0;
  while (~scanf("%d", &n)) {
    ++kase;
    if (n == 1) {
      printf("Case #%d:\n", kase);
      continue;
    }
    priority_queue<Complex> q;
    for (int i = 2; i <= n; ++i)
      if (n % i == 0) {
        while (n % i == 0) n /= i;
        if (i % 4 == 3) q.push(Complex(i));
        else
          for (int a = 1; a * a < i; ++a)
            for (int b = 1; a * a + b * b <= i; ++b)
              if (a * a + b * b == i) {
                q.push(Complex(a, b));
                goto _end;
              }
      _end:;
      }
    printf("Case #%d:", kase);
    while (!q.empty()) {
      Complex now = q.top();
      q.pop();
      printf(" %d", now.re);
      if (now.im == 1) printf("+j, %d-j", now.re);
      else if (now.im) printf("+%dj, %d-%dj", now.im, now.re, now.im);
      putchar(q.empty() ? '\n' : ',');
    }
  }
}