版权声明： 本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！

仓库源文，站点原文

title: "题解 - [POJ 3361] Gaussian Prime Factors" categories:

• 算法竞赛
• 题解 tags:
• 算法竞赛
• 题解
• POJ
• 数学
• 数论
• 复数
• Gauss整数
• Gauss素数 date: 2020-07-27 22:59:46

题目链接

原始题面

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

2
5
6
700

Sample Output

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 素数

代码参考