HDU2650 A math problem—

题意

给你一个数 $a+bj, \ j=\sqrt {-2}$，如果它只能被1、-1、本身和本身的相反数整除，则输出Yes，否则输出No.

分析

高斯整数 $a+bi$ 是素数当且仅当：

(1)$a,b$ 中有一个是0，另一个数的绝对值是形如 $4n+3$ 的素数

(2)$a,b$ 均不为0，而 $a^2+b^2$ 为素数

与判断高斯素数的方法一样，只是将 $j = \sqrt{-1}$ 改成 $j = \sqrt{-2}$，所以把 $a^2+b^2$ 为素数这个条件改成：$a^2 + 2b^2$。$a=b=0$ 的情况还不清楚，但这题的数据不强，随便搞。

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

ll a, b;

bool is_prime(ll x)

{

    bool flag = true;

    for(ll i = ;i*i <= x;i++)

    {

        if(x % i == )

        {

            flag = false;

            break;

        }

    }

    return flag;

}

int main()

{

    while(scanf("%lld%lld", &a, &b) == )

    {

        if(a == )

        {

            //if(b%4 == 3 && is_prime(b))  printf("Yes\n");

            //else  printf("No\n");

             printf("No\n");

        }

        else

        {

            if(is_prime(a*a + *b*b))  printf("Yes\n");

            else  printf("No\n");

        }

    }

    return ;

}

参考链接：

1. https://blog.csdn.net/ACdreamers/article/details/10008107

2. https://blog.csdn.net/keshuai19940722/article/details/36866219

巴特西

HDU2650 A math problem——高斯素数

题意

分析

最新文章

热门文章