博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
模板 - 扩展欧几里得算法
阅读量:4681 次
发布时间:2019-06-09

本文共 1016 字,大约阅读时间需要 3 分钟。

在模数为0或1的时候,会出现一些奇怪的结果。

inline int gcd(int a,int b){    if(b==0)        return a;    else{        while(int i=a%b){            a=b;            b=i;        }        return b;    }}int ex_gcd(int a,int b,int& x,int& y) {    if(b==0) {        x=1;        y=0;        return a;    }    int d=ex_gcd(b,a%b,x,y);    int temp=x;    x=y;    y=temp-a/b*y;    return d;}//解线性同余方程 ax + by = cbool _LCE(int a, int b, int c, int &x0, int &y0) {    int x,y;    int d=ex_gcd(a,b,x,y);    if(c%d!=0){        //无解        return 0;    }    //ax0 + by0 = gcd(a,b)    int k=c/d;    x0=x*k;    y0=y*k;    //(x0,y0)是一组解    //x=x0+bt,y=y0+at,是方程的所有解,对所有整数t成立    return 1;}//解线性同余方程 ax = b mod n//这个是和 ax + ny = b 等价,注意变量int LCE(int a,int b,int n){    //printf("%d*x = %d mod %d\n",a,b,n);    int x,y;    if(_LCE(a,n,b,x,y)){        int t=n/gcd(a,n);        //x0是最小非负整数解        //x=x0+k*t,对任意整数k都是解        int x0=(x%t+t)%t;        return x0;    }    else{        //无解        return -1;    }}

转载于:https://www.cnblogs.com/Yinku/p/10969922.html

你可能感兴趣的文章
C#垃圾回收机制
查看>>
web项目部署到Tomcat服务器的三种方式
查看>>
P1962 斐波那契数列-题解(矩阵乘法扩展)
查看>>
Kibana6.x.x源码分析--Error: $injector:nomod Module Unavailable
查看>>
周围区域问题
查看>>
31、任务三十一——表单联动
查看>>
[ios] IOS文件操作的两种方式:NSFileManager操作和流操作【转】
查看>>
Jenkins之Linux和window配置区别
查看>>
python之hasattr、getattr和setattr函数
查看>>
maven使用阿里镜像配置文件
查看>>
Java之字符流操作-复制文件
查看>>
你好,React setState
查看>>
JS简单表单验证
查看>>
C# 和 c++的语法不同点
查看>>
jquery blockUI 扩展插件 Dialog
查看>>
第一次去CSDN听课感受
查看>>
iOS开发UI篇—实现一个私人通讯录小应用(二)
查看>>
iOS开发UI篇—UITableview控件使用小结
查看>>
lesson1 预备知识
查看>>
Copy code from eclipse to word, save syntax.
查看>>