精华内容
下载资源
问答
  • 高次同余方程求解
    千次阅读
    2019-06-21 21:23:57

    高次同余方程求解

    描述
    解高次同余方程是数论里的一个基础问题。现在邀请你来解一个简单的高次同余方程,xk=1(mod n)。(注:xk=1(mod n)的意思是xk除以n的余数为1)
    数据范围:n和k是整数,且0 < k < n < 1000

    输入
    两个整数,分别为k和n。

    输出
    从小到大输出方程的所有满足0 < x < n的整数解x,每行输出一个。

    样例输入
    3 7

    样例输出
    1
    2
    4

    提示
    需要注意中间计算结果的可能范围。
    (a * b) % p = ((a % p) * (b % p)) % p
    样例输入:
    398 702
    样例输出
    1
    53
    649
    701

    //高次同余方程求解
    #include<iostream>
    using namespace std;
    int main(){
    	int k, n;
    	cin >> k >> n;
    	int res = 1;
    	for (int x = 1; x < n; x++){
    		res = 1;
    		for (int i = 1; i <= k; i++){//求x的k次方
    			res = res*x;
    			res = res%n;//根据提示,取余是为了防止数据溢出
    		}
    		if (res == 1){
    			cout << x << endl;
    		}
    	}
    	return 0;
    }
    
    更多相关内容
  • 原根与指标 ...作用:原根的求解只是求解高次同余方程时计算指标,判断是否有解。 定理5.2.1 设p是奇素数,则模p的原根存在,且有φ(p−1)φ(p-1)φ(p−1)个原根。 定理5.2.2 设p为奇素数,p-1的所有

    原根与指标

    指数与原根

    a e ≡ 1 ( m o d   m ) a^e≡1(mod\ m) ae1(mod m)

    对于上面这个式子

    成立的最小整数e对模m的指数,记做 o r d m ( a ) ord_{m}(a) ordm(a)

    如果a对模m的指数是 φ ( m ) φ(m) φm,则a叫做模m的原根(原根不唯一)。

    作用:原根的求解只是求解高次同余方程时计算指标,判断是否有解。

    定理5.2.1

    设p是奇素数,则模p的原根存在,且有 φ ( p − 1 ) φ(p-1) φp1个原根。

    定理5.2.2

    设p为奇素数,p-1的所有不同素因子为 q 1 , … … , q s q_1,……,q_s q1,,qs则g是模p的原根的充要条件是:
    g p − 1 q i ! ≡ 1 ( m o d   p ) ,    i = 1 , … … , s g^{\frac{p-1}{q_i}}!≡1(mod\ p),\ \ i=1,……,s gqip1!1(mod p),  i=1,s

    例题求模p=43的原根 P 180 P_{180} P180

    1. 得到p-1
    2. 计算 q i q_i qi(为p-1的素因子)
    3. 将g=2,3,5,6,7等带入计算,逐个验证,根据定理5.2.2进行判断。

    PS

    在进行第三部的时候可以通过求其平方的方法进行迭代,或者其他一些小trick

    指标

    g r ≡ a ( m o d   m ) g^r≡a(mod\ m) gra(mod m)

    对于上式来说:

    • g是模m的一个原根
    • a是一个与m互素的整数
    • 存在唯一一个整数r使上式成立

    这个整数r叫做以g为底的a对模m的一个指标,记作 r = i n d g a ( 或 r = i n d a ) r=ind_ga(或r=inda) r=indga(r=inda)

    当我们了解了原根与指标的计算之后就可以进行高次同余方程的学习了

    高次同余方程判断是否有解

    参考 P 196 P_{196} P196
    x n ≡ a ( m o d   m ) x^n≡a(mod\ m) xna(mod m)
    对于这个高次同余式,有解的条件是满足 ( n , φ ( m ) ) ∣   i n d a (n,φ(m))|\ inda n,φm inda,且解数为 ( n , φ ( m ) ) (n,φ(m)) n,φm

    原根的求解只是求解高次同余方程时计算指标,判断是否有解

    所以我们可以记住常见的模p对应的原根:

    23374143
    5263

    在考试的时候直接写出,然后验证其是原根既可。

    得到了原根,我们就可以根据公式三进行计算,得到对应的指标。

    要求学会画对应的指标表,听说模数小的会让我们求,模数大的会提供一个对应的指标表。

    根据 ( n , φ ( m ) ) ∣   i n d a (n,φ(m))|\ inda n,φm inda进行判断,且解数为 ( n , φ ( m ) ) (n,φ(m)) n,φm
    x 12 ≡ 37 ( m o d   41 ) x^{12}≡37(mod\ 41) x1237(mod 41)
    判断出有解之后进行化简:

    mod φ ( 41 ) φ(41) φ41
    12 i n d x ≡ i n d 37 ( m o d   φ ( 41 ) ) = > 12 i n d x ≡ 32 ( m o d   40 ) = > 3 i n d x ≡ 8 ( m o d   10 ) 12indx≡ind37(mod\ φ(41))\\ =>12indx≡32(mod\ 40)\\ =>3indx≡8(mod\ 10) 12indxind37(mod φ(41))=>12indx32(mod 40)=>3indx8(mod 10)
    自己计算得到一个特殊解: i n d x = 6 indx=6 indx=6

    然后计算特解:
    i n d x = 6 + k × 10 ( m o d   40 )     k ∈ Z indx=6+k×10(mod\ 40)\ \ \ k∈Z indx=6+k×10(mod 40)   kZ
    既可得出 i n d x ≡ 6 , 16 , 26 , 36 ( m o d 40 ) indx≡6,16,26,36(mod 40) indx6,16,26,36(mod40)

    通过查表求出对应的 x ≡ 39 , 18 , 2 , 23 ( m o d   41 ) x≡39,18,2,23(mod\ 41) x39,18,2,23(mod 41)

    求解的过程类似于一次同余式:

    image-20211118221820937

    通过查表求出对应的 x ≡ 39 , 18 , 2 , 23 ( m o d   41 ) x≡39,18,2,23(mod\ 41) x39,18,2,23(mod 41)

    求解的过程类似于一次同余式:
    在这里插入图片描述

    展开全文
  • 算法-数论- 高次同余方程与 BSGS 算法.rar
  • 高次同余方程

    千次阅读 2018-05-13 10:16:53
    高次同余方程 A^x ≡ B( mod C ) */ #include &amp;amp;lt;iostream&amp;amp;gt; #include &amp;amp;lt;cstdio&amp;amp;gt; #include&amp;amp;lt;cmath&amp;amp;gt; //#define maxn ...
    /*
    
    解高次同余方程
    
    A^x ≡ B( mod C )
    
    c非素数
    POJ 3243
    */
    
    #include <iostream>
    #include <cstdio>
    #include<cmath>
    //#define maxn 65535
    
    using namespace std;
    
    const int maxn=65535;
    
    struct hash
    {
        int a,b,next;
    }Hash[maxn*2];
    
    int flg[maxn+66];
    int top,idx;
    
    void ins(int a,int b)
    {
        int k=b&maxn;
        if(flg[k]!=idx)
        {
            flg[k]=idx;
            Hash[k].next=-1;
            Hash[k].a=a;
            Hash[k].b=b;
            return ;
        }
        while(Hash[k].next!=-1)
        {
            if(Hash[k].b==b) return ;
            k=Hash[k].next;
        }
        Hash[k].next=++top;
        Hash[top].next=-1;
        Hash[top].a=a;
        Hash[top].b=b;
    }
    
    int find(int b)
    {
        int k=b&maxn;
        if(flg[k]!=idx) return -1;
        while(k!=-1)
        {
            if(Hash[k].b==b)
                return Hash[k].a;
            k=Hash[k].next;
        }
        return -1;
    }
    
    int gcd(int a,int b)
    {
        return b==0?a:gcd(b,a%b);
    }
    
    int exgcd(int a,int b,int& x,int& y)
    {
        if(b==0)
        {
            x=1,y=0;
            return a;
        }
        int r,tx,ty;
        r=exgcd(b,a%b,tx,ty);
        x=ty;
        y=tx-a/b*ty;
        return r;
    }
    
    int inval(int a,int b,int n)
    {
        int x,y,e;
        exgcd(a,n,x,y);
        e=(long long )x*b%n;
        return e<0?e+n:e;
    }
    
    int pow_mod(long long a,int b,int c)
    {
        long long ret=1%c;
        a%=c;
        while(b)
        {
            if(b&1)
                ret=ret*a%c;
            a=a*a%c;
            b>>=1;
        }
        return ret;
    }
    
    int babystep(int A,int B,int C)
    {
        top=maxn;++idx;
        long long buf=1%C,D=buf,K;
        int d=0,tmp;
        for(int i=0;i<=100;buf=buf*A%C,i++)
            if(buf==B)
                return i;
        while((tmp=gcd(A,C))!=1)
        {
            if(B%tmp) return -1;
            ++d;
            C/=tmp;
            B/=tmp;
            D=D*A/tmp%C;
        }
        int M=(int)ceil(sqrt((double)C)),i;
        for(buf=1%C,i=0;i<=M;buf=buf*A%C,i++) ins(i,buf);
        for(int i=0,K=pow_mod((long long)A,M,C);i<=M;D=D*K%C,i++)
        {
            tmp=inval((int)D,B,C);
            int w;
            if(tmp>=0&&(w=find(tmp))!=-1)
                return i*M+w+d;
        }
        return -1;
    }
    
    int main()
    {
        int A,B,C;
        while(scanf("%d%d%d",&A,&B,&C)!=EOF,A||B||C)
        {
            B%=C;
            int tmp=babystep(A,B,C);
            if(tmp<0)
                printf("No Solution\n");
            else
                printf("%d\n",tmp);
        }
        return 0;
    }
    
    /*
    解高次同余方程
    
    A^x ≡ B( mod C )
    
    c  是素数
    时间复杂度O(sqrt(n)*logn)
    POJ 2471
    
    */
    
    #include <cstdio>
    #include <cstring>
    #include <cmath>
    #include <map>
    #include <iostream>
    #include <algorithm>
    using namespace std;
    #define LL long long
    //快速幂求a^b
    LL pow_mod(LL a,LL b,LL n)
    {
        LL s=1;
        while(b)
        {
            if(b&1)
                s=(s*a)%n;
            a=(a*a)%n;
            b=b>>1;
        }
        return s;
    }
    //求解模方程a^x=b(mod n)。n为素数,无解返回-1
    //费马小定理a^(n-1)=1(mod n),n为素数。a^0=1,所以循环节小于等于n,即如果存在解,则最小解x<=n
    LL log_mod (LL a,LL b,LL n)
    {
        LL m,v,e=1,i;
        m=ceil(sqrt(n+0.5));     //x=i*m+j
        //v=inv(pow_mod(a,m,n),n);  //a^m*v=1(mod n)
        v=pow_mod(a,n-m-1,n);
        map<LL,LL>x;
        x[1]=m;
        for(i=1;i<m;i++)  //建哈希表,保存x^0,x^1,...,x^m-1
        {
            e=(e*a)%n;
            if(!x[e])x[e]=i;
        }
        for(i=0;i<m;i++)//每次增加m次方,遍历所有1<=x<=n
        {
            if(x[b])
            {
                LL num=x[b];
                x.clear();//需要清空,不然会爆内存
                return i*m+(num==m?0:num);
            }
            b=(b*v)%n;   //b=b/(a^m)
        }
    
        return -1;
    }
    int main()
    {
        LL a,b,n;
        while(scanf("%I64d%I64d%I64d",&n,&a,&b)!=EOF)
        {
            LL ans=log_mod(a,b,n);
            if(ans==-1)printf("no solution\n");
            else printf("%I64d\n",ans);
        }
        return 0;
    }
    
    展开全文
  • 高次同余方程式的解数及解法

    千次阅读 2013-08-10 19:14:15
    高次同余方程式的解数及解法 分类: 数论2013-07-26 18:41 212人阅读 评论(0) 收藏 举报 定理一: 若是k个两两互质的正整数,,则同余式     (1) 与同余式组     ...

    高次同余方程式的解数及解法

    分类: 数论   212人阅读  评论(0)  收藏  举报

    定理一:

    是k个两两互质的正整数,,则同余式

          

                                        (1)


    与同余式组

          

               (i=1,2,3,...,k)          (2)


    等价,并且若用表示对模的解数,T表示(1)式对模m的解数,


    则:


    所以求多项式的解可以用上述方法,先分解分别求出各个解再合并。



    定理二:p是素数,r>=2是整数,是整系数多项式,设是同余方程


    的一个解,以表示的导数。


    (1)若,则存在整数t,使是同于方程的解。


    (2)若,并且,则对于t=0,1,2,3,...,p-1,中的


    x都是方程的解。



    2013年全国邀请赛长沙赛区的E题就是利用上述的定理。


    题目:Special equations


    题目大意 :

    给定函数 f(x) = a_n x^n + ... + a_1 a + a_0, pri为质数,求一个x使得,f(x) = 0 \mbox{ mod } pri * pri, 如果没有,输出No Solution.


    首先求得所有的i,使得 f(i) = 0 \mbox{ mod } pri

    然后分别验证所有的  x =  i + j * pri ( 0 \le j < pri ) , 是否满足 f(x) = 0 \mbox{ mod } pri * pri

    由于在第一次枚举的时候保留下来的i不会很多,第二次暴力枚举的时候复杂度不会很大。

    [cpp]  view plain copy
    1. #include <iostream>  
    2. #include <string.h>  
    3. #include <stdio.h>  
    4.   
    5. using namespace std;  
    6. typedef long long LL;  
    7.   
    8. const int N=105;  
    9.   
    10. LL a[N];  
    11. LL temp[N];  
    12.   
    13. LL Equ(LL n,LL x)  
    14. {  
    15.     if(n==1)      return a[1]*x+a[0];  
    16.     else if(n==2) return a[2]*x*x+a[1]*x+a[0];  
    17.     else if(n==3) return a[3]*x*x*x+a[2]*x*x+a[1]*x+a[0];  
    18.     else if(n==4) return a[4]*x*x*x*x+a[3]*x*x*x+a[2]*x*x+a[1]*x+a[0];  
    19. }  
    20.   
    21. int main()  
    22. {  
    23.     LL T,n,i,j,p,k,tt=1;  
    24.     cin>>T;  
    25.     while(T--)  
    26.     {  
    27.         cin>>n;  
    28.         for(i=n;i>=0;i--)  
    29.            cin>>a[i];  
    30.         cin>>p;  
    31.         k=0;  
    32.         for(i=0;i<p;i++)  
    33.         {  
    34.             if(Equ(n,i)%p==0)   
    35.             {  
    36.                 temp[k++]=i;  
    37.             }  
    38.         }  
    39.         if(k==0)  
    40.         {  
    41.             printf("Case #%I64d: No solution!\n",tt++);  
    42.             continue;  
    43.         }  
    44.         LL ret=-1;  
    45.         for(i=0;i<k;i++)  
    46.         {  
    47.             bool flag=0;  
    48.             for(j=0;j<p;j++)  
    49.             {  
    50.                 LL x=(temp[i]+j*p);  
    51.                 if(Equ(n,x)%(p*p)==0)  
    52.                 {  
    53.                     ret=x;  
    54.                     flag=1;  
    55.                     break;  
    56.                 }  
    57.             }  
    58.             if(flag) break;  
    59.         }  
    60.         if(ret==-1)  
    61.         {  
    62.             printf("Case #%I64d: No solution!\n",tt++);  
    63.             continue;  
    64.         }  
    65.         printf("Case #%I64d: %I64d\n",tt++,ret);  
    66.     }  
    67.     return 0;  
    68. }  
    展开全文
  • NOI数学:二次同余方程的解法

    千次阅读 2022-02-21 15:13:56
    次同余方程的解 - autoint - 博客园 算法导论-----数论-----计算x^2=1(mod n) 在区间[1,n-1]的解 - Inpeace7 - 博客园 【?】高精版同余方程 【?】高精版同余方程 - 委屈的咸鱼鱼鱼鱼 - 博客园
  • 一、二元一方程 形如的含有两个未知数且最高次数为1的方程我们称之为二元一方程。 很显然,一般的二元一方程的解都是有很多组的,并没有唯一解。 我们先不讨论其他的,尝试一下解方程的整数解:) 我们...
  • 第3章 同余式 3.1 基本概念及一次同余式 3.2 中国剩余定理 3.3 高次同余式的解数及解法 3.4 高次同余式的一般解法 2018-5-17 计算机科学与技术学院 1 3.1 基本概念及一次同余式 定义1 设m是一个正整数,f( x)为多项式...
  • 判断一个数是否为素数:威尔逊定理 ...同余理论:https://blog.csdn.net/sLiubala/article/details/105906999 a≡b( mod n ),c≡b( mod n ),则a +(-) c=b +(-) c (mod n),ac=bd(mod n...
  • 一、同余问题 常用的数论算法(C++描述) 常用的数论算法(C++描述)_linyq@BambooFan ~-CSDN博客_c++数论 数论中的一些基础算法 数论中的一些基础算法_Every day-CSDN博客 常用数论算法 ...
  • 讲解求解同余方程,一个不错的PDF,介绍一次同余方程及一次同余方程组的解的情况及具体求解的方法。
  • 1、求解多元一不定方程 n元一不定方程就是形如∑aixi = C的不定方程,与二元一方程最大的区别是,系数增多,未知数增多。求取变得更复杂。但事实上,多元一方程可以通过消元法来变换成已经完美解决的二元一...
  • 同余定理

    千次阅读 2017-04-21 14:36:40
    同余运算及其基本性质  100除以7的余数是2,意思就是说把100个东西七个七个分成一组的话最后还剩2个。余数有一个严格的定义:假如被除数是a,除数是b(假设它们均为正整数),那么我们总能够找到一个小于b的...
  • 同余运算及其基本性质

    千次阅读 2018-08-11 08:36:32
    同余运算及其基本性质  100除以7的余数是2,意思就是说把100个东西七个七个分成一组的话最后还剩2个。余数有一个严格的定义:假如被除数是a,除数是b(假设它们均为正整数),那么我们总能够找到一个小于b的自然数...
  • n分圆多项式仅包含所有的n单位原根,degΦ_n(x)=φ(n) Φ_1(x)=x-1 # Use ZZ[x];cyclotomic(1,x);cyclotomic(5,x); x -1 x^4 +x^3 +x^2 +x +1 Φ_2(x)=(x^2-1)/Φ_1(x)=x+1 # Use ZZ[x];cyclotomic...
  • 同余的性质

    千次阅读 2017-05-24 08:38:07
    同余运算及其基本性质  100除以7的余数是2,意思就是说把100个东西七个七个分成一组的话最后还剩2个。余数有一个严格的定义:假如被除数是a,除数是b(假设它们均为正整数),那么我们总能够找到一个小于b的...
  • 同余定理与费马(Fermat)小定理

    千次阅读 2018-07-20 00:22:58
    1 同余定理定义 如果两个整数a和b,(a-b)能被m整除,则a和b被m除的余数相同,记做 如果有,则 2 同余定理证明 充分性: 假定(其中r1和r1小于m,h1和h2为整数) a = h1*m+r1 b = h2*m+r2 则a-b = (h1-h2)*m...
  •  作为数学专业出身的我看到这道题当即笑了,因为这是一个很经典的一次同余方程的问题。当然很快就用曾经记得的算法给出了答案41,但我觉得还不过瘾,又因为觉得这类问题对于搞计算机的实在很重要,所以又回忆了一下...
  • 同余运算及其基本性质  100除以7的余数是2,意思就是说把100个东西七个七个分成一组的话最后还剩2个。余数有一个严格的定义:假如被除数是a,除数是b(假设它们均为正整数),那么我们总能够找到一个小于b的...
  • 个数就循环一 证明:由鸽巢定理易证 我们把 r r r 称为 a a a 幂模 m m m 的循环起始点, s s s 称为循环长度。(注意: r r r 可以为0) 用公式表述为: a r ≡ a r + s       ( m o d   m ) a r ≡ ...
  • 线性同余随机发生器

    千次阅读 2014-11-27 17:43:14
     LCG(linear congruential generator)线性同余发生器 伪随机数生成器   LCG 算法数学上基于公式:X(n + 1) = (a * X(n) + c) % m 其中, 各系数为:  模m, m > 0 系数a, 0  增量c, 0  原始值...
  • Miller_Rabin素数测试[Fermat小定理][二探测定理][同余式][Wilson定理] 分类: 各种数学2013-08-14 19:06 444人阅读 评论(0) 收藏 举报 目录(?)[+] 部分引用自: ...
  • 求同余方程x^A=B(mod m)的解个数(原根与...分析:设,那么上述方程解的个数就与同余方程组:的解等价。 设同于方程的解分别是:,那么原方程的解的个数就是 所以现在的关键问题是求方程:的解个数。
  • 中国剩余定理编程实现

    千次阅读 2017-02-16 14:55:30
    这部中世纪的数学杰作,在许多方面都有创造,其中求解一次同余组的“大衍求一术”和求高次方程数值解的“正负开方术”,更是具有世界意义的成就。秦九韶在《数书九章》中明确地系统地叙述了求解一次同余组的一般计算...
  • 信息安全数学基础题型及知识点(数论部分)

    万次阅读 多人点赞 2018-12-20 14:06:34
    4.求解高次同余式 3. 求解二元一次同余方程组 (大致和解二元一次方程组类似) 第四章 二次同余式和平方剩余 1.求平方剩余和平方非剩余 2.模为奇素数的平方剩余与平方非剩余 3. 勒让德符号,雅克比符号 4. 模p平方根...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 253,142
精华内容 101,256
关键字:

高次同余