系统 网站开发工程师,如何给网站做流量,网页跳转到其它网站,wordpress国内几大主题正式叙述前还写了一点自己的小感受。
问题#xff1a;求两个正整数a#xff0c;b的最大公约数。
大神看来是很简单的问题#xff0c;但是对于去年夏天刚学python的我来说#xff0c;这是个很难的问题#xff0c;还记得当时一晚上睡不着都在想怎么快一点的求出最大公约数…正式叙述前还写了一点自己的小感受。
问题求两个正整数ab的最大公约数。
大神看来是很简单的问题但是对于去年夏天刚学python的我来说这是个很难的问题还记得当时一晚上睡不着都在想怎么快一点的求出最大公约数后来猜测最小公倍数的求法还有最后想出来的欣喜若狂我现在还记忆犹新。 还记得看过一个小梗一个农民种着种着地一排一排的种突然陷入深思沉思良久回去算了很久以后借了钱疯了似的坐火车跑到中科院门口等来数学系教授向他讲述了自己的重大发现。大概意思就是自己从田地中大彻大悟发明了一种快速计算方法不用计数不用加法不用数学还给了教授一张伟大的定律表。
教授告诉他你真的很厉害你的发现很伟大能在种田中悟出来这种算法可不容易。 但是你发明的这种算法叫乘法你给我的表完善一下以后叫九九乘法表。
农民继续回去种田
这个故事告诉我们要多虚心接受知识不要老自己想。。。。 我知道了欧几里得算法以后感觉自己就跟这个农民一样。。。。。。。
不过知道了自己的想法就是欧几里得算法时还是挺高兴的。。。
就当锻炼思维了吧。。只能这么安慰自己。 好开始正题。。。。 我当时的思路是这样的求ab的最大公约数假设最大公约数是x的话a一定可以用i*x来表示b也一定可以用j*x来表示我们怎么把i和j去掉把x榨出来呢
让这俩数不断互相相减就可以啦
后来自己想到了互相取余。 我们来看正规的欧几里得算法
首先放简介欧几里德算法又称辗转相除法是指用于计算两个正整数ab的最大公约数。应用领域有数学和计算机两个方面。计算公式gcd(a,b) gcd(b,a mod b)。
看代码实现
Python
def gcd(a, b):while a ! 0:a, b b % a, areturn b 后来知道了欧几里得还有拓展
可以用来求二元一次方程的通解还可以用来求乘法逆元。
已知整数a、b扩展欧几里得算法可以在求得a、b的最大公约数的同时能找到整数x、y其中一个很可能是负数使它们满足贝祖等式axbygcd(a,b)
如果a是负数可以把问题转化成|a|(-x)bygcd(|a|,b) 然后令x(-x)。
//返回 dgcd(a,b); 和对应于等式 axbyd 中的 x,y
long long extend_gcd(long long a,long long b,long long x,long long y)
{if(a0b0) return −1;//无最大公约数if(b0){x1;y0;return a;}long long dextend_gcd(b,a%b,y,x);y−a/b*x;return d;
}
求逆元真的不想叙述了上个代码算了 //********* 求逆元 *******************
//ax 1(mod n)
long long mod_reverse(long long a,long long n)
{long long x,y;long long dextend_gcd(a,n,x,y);if(d1) return (x%nn)%n;else return −1;
}
逆元利用欧拉
mod 为素数, 而且 a 和 m 互质
long long inv(long long a,long long mod)//为素数mod
{return pow_m(a,mod−2,mod);
}
