首页 > 代码库 > UVA 1415 - Gauss Prime(数论,高斯素数拓展)

UVA 1415 - Gauss Prime(数论,高斯素数拓展)

UVA 1415 - Gauss Prime

题目链接

题意:给定a + bi,判断是否是高斯素数,i = sqrt(-2)。

思路:普通的高斯素数i = sqrt(-1),判断方法为:
1、如果a或b为0,判断另一个数为4 * n + 3形式的素数(用到费马平方和定理)
2、如果a、b都不为0,判断a ^ 2 + b ^ 2 是否为素数

那么这题,提取出sqrt(2)来,就和基本情况一样了。
对于2,变成: 如果a、b都不为0,判断a ^ 2 + 2 b ^ 2是否为素数
对于1有点不同,变成x ^ 2 + 2
y ^ 2形式,不在适用费马平方和定理,由于a,b最大才1W,完全可以去枚举,判断能不能拆成x ^ 2 + 2 * y ^ 2形式。这样一来问题就解决了

代码:

#include <stdio.h>
#include <string.h>
#include <math.h>

const int N = 20005;
int t, a, b, prime[N], pn = 0, vis[N];

bool judge() {
    if (a == 0) {
	int m = sqrt(m);
	for (int i = 0; i <= m; i++) {
	    double t = sqrt((b - i * i) * 1.0 / 2);
	    if (ceil(t) == floor(t)) return true;
	}
	return false;
    }
    int tmp = a * a + 2 * b * b;
    for (int i = 0; i < pn && prime[i] < tmp; i++)
	if (tmp % prime[i] == 0) return false;
    return true;
}

int main() {
    vis[1] = 1;
    for (int i = 2; i < N; i++) {
	if (vis[i]) continue;
	prime[pn++] = i;
	for (int j = i * i; j < N; j += i) {
	    vis[j] = 1;
	}
    }
    scanf("%d", &t);
    while (t--) {
	scanf("%d%d", &a, &b);
	printf("%s\n", judge()?"Yes":"No");
    }
    return 0;
}