正文 

当前位置： 首页 > java > java教程

数论学习之欧几里得的应用

Soda Soda     2022-08-12     441

关键词：

扩展欧几里德算法的应用：1.求二元一次方程 ax + by = c 的整数解

定理：对于整数方程ax + by = c，若c mod Gcd(a, b) == 0，则该方程存在整数解，否则不存在整数解。

    设d = gcd(a,b), a‘ = a/d,  b‘ = b/d, 则方程变形为 d(a‘x + b‘y) = c
    若方程有整数解，则 d|c, 否则无解.
    设c‘ = c/d, 则方程 ax + by = c等价于 a‘x + b‘y = c‘
    因为gcd(a‘,b‘) = 1, 则我们可以求得 a‘x + b‘y = gcd(a‘,b‘) = 1 的解，

    即 ax + by = gcd(a,b) = d的解 x，y。
    则c‘x, c‘y就是 ax + by = c 的一组解。
    xx = c‘x + b‘t,  yy = c‘y - a‘t   t∈Z就是所有满足条件的解。

  1. #include<cstdio>  
  2.   
  3. int x,y,a,b,c;  
  4.   
  5. int extended_euclid(int a,int b,int &x,int &y)    
  6. {    
  7.     if(b==0)  //即gcd(a,b)=a     
  8.     {    
  9.         x=1;y=0;    
  10.         return a;    
  11.     }    
  12.     int n=extended_euclid(b,a%b,x,y);  //最大公约数相等      
  13.     int k=x;    
  14.     x=y;    
  15.     y=k-a/b*y;    
  16.     return n;    
  17. }    
  18.    
  19. bool kk(int a,int b,int c,int &x,int &y)  //ax+by=c     
  20. {    
  21.     int n=extended_euclid(a,b,x,y);    
  22.     if(c%n) return 0;  //c不是最大公约数时无解      
  23.     int k=c/n;    
  24.     x*=k;y*=k;    
  25.     return 1;    
  26. }    
  27. int main()  
  28. {  
  29.     scanf("%d%d%d",&a,&b,&c);  
  30.     if(!kk(a,b,c,x,y)) printf("Impossible ");  
  31.     else printf("x=%d y=%d ",x,y);  
  32.     return 0;  
  33. } 

之前的是摘抄，下面都是自己的感悟：
求解方程 a*x ≡ b (mod n)

e      a*x – y*n = b,这个就是二元一次方程组，用扩欧

e      如果方程有解，则b%(gcd(a,b))==0，如果不为0，则代表无解

e      否则用扩欧(a,n,x,y);,解出一组x,y  代表a*x – y*n = b

 

下面给出一份求解a*x ≡ 1 (mod b) 的最小整数解的代码

#include <iostream>

#include <stdio.h>

#include <algorithm>

using namespace std;

int ex1 (int a,int b,int &x,int &y)

{

         if (b == 0)

         {

                   x = 1,y = 0;

                   return a;

         }

         else

         {

                   int gcd1 = ex1(b,a%b,x,y);//

                   int k = x;

                   x = y;

                   y = k-(a/b)*y;

                   return gcd1;

         }

}

int main ()

{

    int a,b,x,y;

    cin >>a>>b;

    int ans = ex1 (a,b,x,y);

    if (1%ans!=0)cout <<"No answer"<<endl;

    else

    {

        x = x%b;

        while (x<0)x+=b;

        cout <<x<<endl;

    }

    return 0;

}

数论学习之费马与欧拉

数论复习之费马与欧拉QB_UDG 2016年11月8日10:16:181.费马小定理FermatTheory如果p是素数，且a与p互质，即gcd(a,p)=1  那么(a^p-1)≡1(modp)应用： 求乘法逆元 乘法逆元:(x*x’)≡ 1 (modp)称x’为x模p的乘法逆元 (注... 查看详情

数论及其应用——欧几里得算法

 欧几里得是数论当中最基本的定理，以其为基础的拓展欧几里得算法在解决同余方程、求模逆元等问题。  首先来介绍几个概念，数论当中一些基本的概念其实在小学就学过，但是很长一段时间并没有用到它们，因此... 查看详情

信息学中的数论

...我兴奋不已。这一篇让我来聊一聊我学过的gcd，lcm，扩展欧几里得算法，逆元，组合数等。这篇贴的代码都是未经过编译运行的，所以如果有错或有疑问请评论。恩那么什么是数论和数学有关的非几何都是数论？嘛，我也不知道... 查看详情

数论学习之乘法逆元

用法：用于除法取模思路:扩欧要求：b、p互质设k为b的乘法逆元：则在求解除法取模问题时：有(a/b)%p=>(a*k)%p当b很大时，用除法会出现精度问题。。so 乘法逆元：如果b*k≡1（modp）则称k是b关于p的乘法逆元 我们可以通过... 查看详情

初等数论-base-1(筛法求素数，欧拉函数，欧几里得算法)(代码片段)

前言初等数论在OI中应用的基础部分，同机房的AuSquare和zhou2003君早就写完了，一直划水偷懒的Hk-pls表示很方，这才开始了这篇博客.$P.S.$可能会分部分发表。筛法求素数埃式筛素数问题：求$[1,n]$中的所有素数总体思路就是在$[2,n]$... 查看详情

数论扩展欧几里得算法

扩展欧几里得  上回刚写完欧几里得，那现在还有一个东西叫拓展欧几里得：  扩展欧几里得法是一个在求解同余方程等问题上的一个很好的方法，其具体功能如下：  在已知(a,b)时，求解一组(p,q)使得p*a+q*b=... 查看详情

数论（欧几里得，扩展欧几里得，欧拉）

　　今天考试了，三道题分别是求欧拉，逆欧拉，欧拉求和　　对于我这样的蒟蒻来说，我选择狗带。　　爆零稳稳的。　　现在整理一下；　　φ(n)(欧拉函数值)为不大于n的正整数中与n互质的数的个数；　　有几条这样的性质... 查看详情

json学习之jsonarray的应用（转载）

从json数组中得到相应java数组，如果要获取java数组中的元素，只需要遍历该数组。1/**2*从json数组中得到相应java数组3*JSONArray下的toArray()方法的使用4*@paramstr5*@return6*/7publicstaticObject[]getJsonToArray(Stringstr){8JSONArrayjsonArray=JSONArray.fromO 查看详情

机器学习之推荐算法(代码片段)

1、知识点"""推荐系统1、相似度计算：1、欧几里德距离2、皮尔逊相关系数3、Cosin距离2、推荐相似度选择：1、固定数量的邻居2、基于相似度门槛的邻居3、基于用户的协同过滤：根据用户和其他用户之间的相关系数值，选择值越... 查看详情

jzyzoj1371青蛙的约会扩展欧几里得gtmd数论

http://172.20.6.3/Problem_Show.asp?id=1371http://www.cnblogs.com/jackge/archive/2013/04/22/3034925.html详细的题解，大概是网上能看到的最简单易懂的扩展欧几里得讲解了 代码1#include<iostream>2#include<cstdio>3#include&l 查看详情

jquery学习之ajax应用

1.AJAX=异步javaScript和XML：在不重载整个网页的情况下，AJAX通过后台加载数据，并在网页上进行显示 2.load():简单但强大的AJAX方法，load()方法从服务器加载数据，并把返回的数据放入被选元中；语法：$(selector).load(URL,data,callback)... 查看详情

数论，类欧几里得算法

类欧几里得部分转载自不来也不去的一只失忆蝴蝶。%%%  查看详情

poj2142thebalance数论（扩展欧几里得算法）

...问题转化为求满足方程ax+by=c，|x|+|y|的最小值。先用扩展欧几里得算法求得通解。由原方程得答案分布在y=-a/b*x+c/b（a>0,b>0,c>0），因此是k<0, 查看详情

acm数论-欧几里得与拓展欧几里得(代码片段)

ACM数论——欧几里得与拓展欧几里得 欧几里得算法：　　欧几里德算法又称辗转相除法，用于计算两个整数a,b的最大公约数。　　基本算法：设a=qb+r，其中a，b，q，r都是整数，则gcd(a,b)=gcd(b,r)，即gcd(a,b)=gcd(b,a%b)。intgcd(inta,in... 查看详情

数论逆元求解（扩展欧几里得算法+费马小定理）

看数论看得头皮发麻，o(╥﹏╥)o，总算理解了一些东西。（推荐一个dalao博客，个人感觉他的博客易懂点，可能是那些颜文字的作用（逃...））在看逆元之前我们先来看个同余方程的定理吧 同余定理：a和b取余p得到相同的余... 查看详情

理论：数论：拓展欧几里得算法及其证明

拓展欧几里得算法算法描述定义1.7.算法证明记,对a，b使用欧几里得定理得：.在这里我们代入，将上式改写成：.我们将上式逐一向前代回，就将得到rk关于a和b的线性组合。.算法推论拉梅定理：用欧几里得... 查看详情

驱动学习之驱动和应用的接口

 在前面讲过，驱动层是应用层是分离，驱动层的代码不能使用再应用层，应用层也不能直接操作驱动代码，那么应用层和驱动层之间是如何来实现数据间的交换的能，方法就是通过相应的接口函数。（1）copy_from_userunsigned&nbs... 查看详情

angularjs学习之模块

1.模块定义了一个应用程序；模块是应用程序中不同部分的容器；模块是应用控制器的容器；控制器通常属于一个模块 2.创建模块：你可以通过AngularJS的angular.module函数来创建模块： <divng-app="myApp">...</div><script&... 查看详情