版权声明： 本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！
title: "题解 - [UVa 1415] Gauss Prime" categories:
In the late 1700s’, Gauss, a famous mathematician, found a special kind of numbers. These integers are all in the form: $a + b\sqrt{-k}$. The sum and multiplication of these integers can be naturally defined as the follows:
$$ (a + b\sqrt{-k}) + (c + d\sqrt{-k})= (a + c) + (b + d)\sqrt{-k} $$
$$ (a + b\sqrt{-k}) \times (c + d\sqrt{-k}) = (a \times c + b \times d \times k) + (a \times d + b \times c)\sqrt{-k} $$
One can prove that the sum and multiplication of these integers constitute the structure called "imaginary quadratic field" in calculus
In case $k = 1$, these are common complex numbers
In case both $a$ and $b$ are integers, these numbers are called "Gauss integers", and this is the very case that interests people the most in quadratic algebra
As we all know that every integer can be factorized into the multiplication of several primes (Fundamental theorem of arithmetic, or unique factorization theorem)
Primes are the integers that can only be divided by 1 and itself. We do have a similar concept in the context of Gauss integer
If a Gauss integer cannot bee factorized into the multiplication of other Gauss integers ($0, 1, -1$ exclusive), we call it a "Gauss Prime" or "Non-divisible"
Please note that $0$, $1$ and $-1$ are not regarded as gauss primes but $\sqrt{-k}$ is
However, unique factorization theorem doesn’t apply to arbitrary $k$. For example in the case $k = 5$, $6$ can be factorized in two different ways: $6 = 2 \times 3, 6 = (1 + \sqrt{-5}) \times (1 - \sqrt{-5})$
Thanks to the advance of mathematics in the past 200 years, one can prove that there are only $9$ integers can be used as $k$, such that the unique factorization theorem satisfies. These integers are $k ∈ {1, 2, 3, 7, 11, 19, 43, 67, 163}$
The first line of the input is an integer $n$ ($1 < n < 100$), followed by $n$ lines. Each line is a single case and contains two integers, $a$ and $b$ ($0 ≤ a ≤ 10000, 0 < b ≤ 10000$)
To make this problem not too complicated, we just suppose that $k$ is $2$
For every case of the input, judge whether $a + b\sqrt{-2}$ is a gauss prime
Output the answer ‘Yes’ or ‘No’ in a single line
Please note that $(5, 1)$ is not a gauss prime because $(5, 1) = (1, -1) \times (1, 2)$
2
5 1
3 4
No
Yes
定义
令 $k=2$, 此时的 Gauss 整数也满足素数唯一分解定理, 给出多组整数 $a,b$, 输出 $a+b\sqrt{-2}$ 是否为 Gauss 素数
本题中对 Gauss 素数进行了重定义, 通常意义下的 Gauss 素数是在 $\mathbb{Z}[\sqrt{-1}]$ 中的, 同样满足素数唯一分解定理
通常意义下判定 Gauss 素数的方法如下
本题中则变化为