精华内容
下载资源
问答
  • 而判断其为高斯素数的条件是,它不能再分解为其他高斯整数的乘积(0,1,-1除外),因为0,-1和1不能被视为高斯素数,但在这个题目中sqrt(-2)是高斯素数 所以高斯素数有以下两个性质: 如果一个素数,那么该素数p...

    题目链接:点击查看

    题目大意:给出一组a和b,判断a+b*sqrt(-2)是不是高斯素数

    题目分析:对于一般的复数a+b*i,我们判断其为高斯整数的条件为a和b都为整数即可

    而判断其为高斯素数的条件是,它不能再分解为其他高斯整数的乘积(0,1,-1除外),因为0,-1和1不能被视为高斯素数,但在这个题目中sqrt(-2)是高斯素数

    所以高斯素数有以下两个性质:

    1. 如果一个素数p\equiv 3(mod\ 4),那么该素数p就是一个高斯素数
    2. 对于高斯整数a+b*j,如果该高斯整数的范式:a*a+b*b是一个素数,那么a+b*j是一个高斯素数

    现在回到这个题目上来,这个题目将sqrt(-1)变为了sqrt(-2),也就是说分为了两种情况讨论:

    1. a==0时,则a+b*sqrt(-2)一定不是高斯素数,因为b*sqrt(-2)肯定可以分解
    2. a!=0时,则判断其范式(a*a+b*b*2)是否是素数即可

    因为这个题目中的b保证不等于0了,所以就不用判断p\equiv 3(mod\ 4)这个条件了

    实现代码:用试除法模拟即可

    #include<iostream>
    #include<cstdio> 
    #include<string>
    #include<ctime>
    #include<cstring>
    #include<algorithm>
    #include<stack>
    #include<queue>
    #include<map>
    #include<sstream>
    using namespace std;
    
    typedef long long LL;
    
    const int inf=0x3f3f3f3f;
    
    const int N=15;
    
    bool is_prim(int x)
    {
    	for(int i=2;i*i<=x;i++)
    		if(x%i==0)
    			return false;
    	return true;
    } 
    
    int main()
    {
    //	freopen("input.txt","r",stdin);
    	int w;
    	cin>>w;
    	while(w--)
    	{
    		int a,b;
    		scanf("%d%d",&a,&b);
    		if(a==0)
    		{
    			printf("No\n");
    			continue;
    		}
    		if(is_prim(a*a+b*b*2))
    			printf("Yes\n");
    		else
    			printf("No\n");
    	}
    	
    	
    	
    	
    	
    	
    	
    	
    	
    	
    	return 0;
    }

     

    展开全文
  • 题目大意:给出一个a,b,表示高斯数a+bi(i=−2‾‾‾√,推断该数是否为高斯素数。 解题思路; a = 0 时。肯定不是高斯素数a != 0时,推断a2+2b2是否为素数就可以。 #include <cstdio> #include <...

    题目链接:uva 1415 - Gauss Prime

    题目大意:给出一个a,b,表示高斯数a+bi(i=2,推断该数是否为高斯素数。

    解题思路;

    • a = 0 时。肯定不是高斯素数
    • a != 0时,推断a2+2b2是否为素数就可以。
    #include <cstdio>
    #include <cstring>
    #include <cmath>
    
    bool is_prime (int n) {
        int m = sqrt(n+0.5);
        for (int i = 2; i <= m; i++)
            if (n % i == 0)
                return false;
        return true;
    }
    
    bool judge (int a, int b) {
        if (a == 0)
            return false;
        return is_prime(a*a+2*b*b);
    }
    
    int main () {
        int cas;
        scanf("%d", &cas);
        while (cas--) {
            int a, b;
            scanf("%d%d", &a, &b);
            printf("%s\n", judge(a, b) ?

    "Yes" : "No"); } return 0; }

    转载于:https://www.cnblogs.com/lcchuguo/p/5128654.html

    展开全文
  • 高斯整数 a=x+y∗i  (x,y∈Z)a = x+y*i\ \ (x,y\in Z)a=x+y∗i  (x,y∈Z),则 aaa 为高斯整数。 aaa 的范为 N(a)=∣a2∣=x2+y2N(a)=|a^2|=x^2+y^2N(a)=∣a2∣=x2+y2。 若存在高斯整数 yyy,...

    前言

    如果你对这篇文章可感兴趣,可以点击「【访客必读 - 指引页】一文囊括主页内所有高质量博客」,查看完整博客分类与对应链接。

    高斯整数

    • a = x + y ∗ i    ( x , y ∈ Z ) a = x+y*i\ \ (x,y\in Z) a=x+yi  (x,yZ),则 a a a 为高斯整数。
    • a a a 的范为 N ( a ) = ∣ a 2 ∣ = x 2 + y 2 N(a)=|a^2|=x^2+y^2 N(a)=a2=x2+y2
    • 若存在高斯整数 y y y,使得 a y = 1 ay=1 ay=1,则 a a a 为高斯整数中的乘法可逆元, y y y a a a 的逆。
    • 高斯整数 a a a 是可逆元的充要条件是 N ( a ) = 1 N(a)=1 N(a)=1,高斯整数中只有 4 4 4 个可逆元,分别是 − 1 、 1 、 i 、 − i -1、1、i、-i 11ii
    • a 、 b a、b ab 为高斯整数, a = b y a=by a=by,则 a a a b b b 等价,即 a = b 、 − b 、 i b 、 − i b a=b、-b、ib、-ib a=bbibib

    高斯素数

    • 定义:设 ϕ \phi ϕ 为高斯整数中的非零非可逆元,则 ϕ \phi ϕ 为高斯素数。即 ϕ \phi ϕ 的因子或者为可逆元,或者是与 ϕ \phi ϕ 等价的高斯整数。
    • ϕ \phi ϕ 为高斯整数,且 N ( ϕ ) = p N(\phi)=p N(ϕ)=p 为素数,则 ϕ \phi ϕ 必定为高斯素数。
    • ϕ \phi ϕ 为高斯素数,则其共轭元也是高斯素数。

    高斯素数判断

    • 高斯整数 a + b i a+bi a+bi 是素数,当且仅当:
    1. a 、 b a、b ab 中有一个是零,另一个数的绝对值是形如 4 ∗ n + 3 4*n+3 4n+3 的素数。
    2. a 、 b a、b ab 均不为零,而 a 2 + b 2 a^2+b^2 a2+b2 为素数。

    费马平方和定理

    • 奇质数能表示为两个平方数之和的充分必要条件是该质数被 4 4 4 除余 1 1 1,即 4 ∗ n + 1 4*n+1 4n+1
    • 例题:找出 [ l , r ] [l,r] [l,r] 中的素数 t t t,满足 t = a 2 + b 2    ( a , b ∈ N ∗ ) t=a^2+b^2\ \ (a,b\in N^{*}) t=a2+b2  (a,bN),输出这种素数总数。
    展开全文
  • HDU 2650 判断是a+bj 是否为高斯素数

    千次阅读 2015-11-04 20:36:15
    高斯素数的判断

    题意:给出,其中,判断是否为高斯素数。

     

    分析:其实就是上面的判断高斯素数的方法,但是注意一点,这里,而正常情况是,其实差不多一样,

    只是把为素数这个条件改为:为素数即可,那么如果把题目描述改为呢?同样的道理只需把

    判断条件改成为素数即可,由于很大,所以写个Miller_Rabin吧。。。





    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include <iostream>
    
    const int Times=10;
    
    using namespace std;
    typedef long long LL;
    
    LL multi(LL a,LL b,LL m)
    {
        LL ans=0;
        while(b)
        {
            if(b&1)
            {
                ans=(ans+a)%m;
                b--;
            }
            b>>=1;
            a=(a+a)%m;
        }
        return ans;
    }
    
    LL quick_mod(LL a,LL b,LL m)
    {
        LL ans=1;
        a%=m;
        while(b)
        {
            if(b&1)
            {
                ans=multi(ans,a,m);
                b--;
            }
            b>>=1;
            a=multi(a,a,m);
        }
        return ans;
    }
    
    bool Miller_Rabin(LL n)
    {
        if(n==2) return true;
        if(n<2||!(n&1)) return false;
        LL a,m=n-1,x,y;
        int k=0;
        while((m&1)==0)
        {
            k++;
            m>>=1;
        }
        for(int i=0; i<Times; i++)
        {
            a=rand()%(n-1)+1;
            x=quick_mod(a,m,n);
            for(int j=0; j<k; j++)
            {
                y=multi(x,x,n);
                if(y==1&&x!=1&&x!=n-1) return false;
                x=y;
            }
            if(y!=1) return false;
        }
        return true;
    }
    
    int main()
    {
        LL a,b;
        while(~scanf("%I64d%I64d",&a,&b))
        {
            if(a==0)
            {
                if(b%4==3&&Miller_Rabin(b)) puts("Yes");
                else  puts("No");
            }
            else
            {
                LL t=a*a+2*b*b;
                if(Miller_Rabin(t)) puts("Yes");
                else  puts("No");
            }
        }
        return 0;
    }
    

    展开全文
  • poj 3361 Gaussian Prime Factors题意:在复数 a+bj (a,b为整数)范围内,约数只有 1, -1, a+bj, -(a+bj)的称为高斯素数。求任给正整数N的所有素因子(|b|>a>0)。默认N解法:定理有云: n≡3(mod 4)者,无因式分解。 ...
  • 题目 求一个给定的圆(x2+y2=r2x^2+y^2=r^2x2+y2=r2...然后我们要找出哪些符合题意,首先2是不可以的,而且高斯素数不可以表示成两个数的平方和,所以说只能是(4i+1)(4i+1)(4i+1)型素数,于是质因数分解 代码 #inclu...
  • 题意:判断a+b*sqrt(-2)是否为素数 解法:参考高斯素数的定义即判断方法 http://zh.wikipedia.org/wiki/高斯整數#include<stdio.h>
  • #include #include #include #include using namespace std; int ok(int x) { for(int i=2;i(int)sqrt(x+0.5);i++) { if(x%i==0) return 0; } return 1; } int main() { int T,a,b;... wh
  • http://zh.wikipedia.org/wiki/高斯整數 转载于:https://www.cnblogs.com/luotinghao/archive/2012/11/22/2782434.html
  • 题意:给定a + bi,推断是否是高斯素数,i = sqrt(-2)。 思路:普通的高斯素数i = sqrt(-1),推断方法为: 1、假设a或b为0。推断还有一个数为4 * n + 3形式的素数(用到费马平方和定理) 2、假设a、b都不为0,推断a...
  • 利用高斯素数的性质,将一个数分解成其质因数相乘的形式之后(唯一分解定理),若其中的质因数可以分解为高斯素数,则对答案的贡献就是其指数+1。那怎么判断一个数是不是高斯素数呢? 1.满足4n+1的质因数可以分解为...
  • 型的质数高斯质数,不可再分解,也就不存在共轭复数,那么必须要偶数次幂才能使得两边最后的乘积仍是共轭复数,且只有一种组合方式,若为奇数次幂,则不存在整点。 特殊质数 2: 前面并没有考虑 2,它既不是 ...
  • 【学习笔记】高斯整数(全部相关概念及例题详解)
  • uva1415 - Gauss Prime 高斯素数

    千次阅读 2014-07-01 14:02:57
    √-2,因为素数不一定是高斯素数,当a=0或b=0时,素数也有可能分解成 (a+b √-2)*( a-b √-2)(素数如果能分解,只能是这种形式),费马定理不能用了,就暴力看有没有b=x*x+2*y*y。  如果a,b都不为零,就...
  • 题目要求一个数的高斯素数约数 高斯素数的性质(不知道真不能做) 一个素数,若该数能写成 4n+3那么便是一个高斯素数 复数a+bj,若a^2+b^2也是一个素数那该复数便是一个高斯素数 于是对给出的数进行素数...
  • 就可以了,但是有情况是r本身是一个大素数,或是一个大素数*小素数,所以晒完之后再特判一下就可以了。 代码如下 #include #include #define LL long long using namespace std; LL n, m ,Ans= 1 ,p...
  • 表示 :n 以内,i 是素数或 i 的最小素因子大于 p j p_j p j ​ ,i 是 4 n + 3 4n + 3 4 n + 3 类型的数 g 1 ( n , 0 ) = n − 1 4 , g 3 ( n , 0 ) = n + 1 4 g1(n,0) = \frac{n - 1}{4},g3(n,0) = \frac{n...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 5,093
精华内容 2,037
关键字:

高斯素数