gcd 模板

声明

  给 x,y 两个数,求 x,y 的最大公因数。

  辗转相除法,直接套!!!

 function gcd(x,y:longint):longint;
begin
if y= then exit(x) else exit(gcd(y,x mod y));
end;
 int gcd(int x,int y)
{
if (y==) return x; else return gcd(y,x%y);
}

  下面给出 exgcd 做法(对于上面的 ax+by=m 来说,我们并不仅仅想要知道有没有解,而是想要知道在有解的情况下这个解到底是多少):传送门

 #include<iostream>
#include<cstdio>
#include<cmath> using namespace std; int exgcd(int a,int b,int &x,int &y)//扩展欧几里得算法
{
if(b==)
{
x=;y=;
return a; //到达递归边界开始向上一层返回
}
int r=exgcd(b,a%b,x,y);
int temp=y; //把x y变成上一层的
y=x-(a/b)*y;
x=temp;
return r; //得到a b的最大公因数
}
————————————————
版权声明:本文为CSDN博主「_Warning_」的原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接及本声明。
原文链接:https://blog.csdn.net/destiny1507/article/details/81750874

  同余相关

上一篇:Python WMI获取Windows系统信息


下一篇:[置顶] Android中使用sqlite3操作SQLite