题解 - [UVa 1415] Gauss Prime

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

题目链接

原始题面

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\}\)

Input

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\))

Output

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

Sample Explanation

Please note that \((5, 1)\) is not a gauss prime because \((5, 1) = (1, -1) \times (1, 2)\)

Sample Input

1
2
3
2
5 1
3 4

Sample Output

1
2
No
Yes

题意简述

定义

  • Gauss 整数: \(\mathbb{Z}[\sqrt{-k}]:=\{a+b\sqrt{-k}|a,b\in\Bbb{Z}\}\) 中的数
  • Gauss 素数：不能分解成其他 (除 \(0,1,-1\) 外) Gauss 整数乘积的 Gauss 整数
    • 注意: \(0,1,-1\) 不是 Gauss 素数，但 \(\sqrt{-k}\) 是 Gauss 素数

令 \(k=2\), 此时的 Gauss 整数也满足素数唯一分解定理，给出多组整数 \(a,b\), 输出 \(a+b\sqrt{-2}\) 是否为 Gauss 素数

解题思路

本题中对 Gauss 素数进行了重定义，通常意义下的 Gauss 素数是在 \(\mathbb{Z}[\sqrt{-1}]\) 中的，同样满足素数唯一分解定理

通常意义下判定 Gauss 素数的方法如下

  • 若 \(a=0\) 或 \(b=0\), 若另一个非 \(0\) 数模 \(4\) 余 \(3\), 则该数不可拆分成两整数的平方和，说明此数为 Gauss 素数
  • 若 \(a,b\ne0\), 若 \((a+bi)(a-bi)=a^2+b^2\) 为素数，则此数为 Gauss 素数

本题中则变化为

  • 若 \(a=0\), 则 \(a+b\sqrt{-2}=b\cdot\sqrt{-2}\), 其不是 Gauss 素数
  • 若 \(a,b\ne0\), 若 \((a+b\sqrt{-2})(a-b\sqrt{-2})=a^2+2b^2\) 为素数，则此数为 Gauss 素数

代码参考

Show code

UVA_1415view 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
/*
 * @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 <cstring>
const int N = 2e4 + 5;
bool vis[N];
int pri[N], cnt_pri = 0;
bool judge(int a, int b) {
  if (a == 0) return 0;
  int _ = a * a + 2 * b * b;
  for (int i = 0; i < cnt_pri && pri[i] < _; ++i)
    if (_ % pri[i] == 0) return 0;
  return 1;
}
int main() {
  vis[1] = 1;
  for (int i = 2; i < N; ++i) {
    if (vis[i]) continue;
    pri[cnt_pri++] = i;
    for (int j = i * i; j < N; j += i) { vis[j] = 1; }
  }
  int kase;
  scanf("%d", &kase);
  while (kase--) {
    int a, b;
    scanf("%d%d", &a, &b);
    printf("%s\n", judge(a, b) ? "Yes" : "No");
  }
  return 0;
}