数论篇 -  - 欧几里得算法,扩展欧几里得算法,线性同余方程,
ACM, 数论 0 评论 0 浏览
欧几里得算法:
gcd(a,b)=gcd(b,a mod b)
a<b gcd(b,a mod b)=gcd(b,a)=gcd(a,b) 命题成立
a>=b 设a=q*b+r (0<=r<b) r=a mod b,对于a,b的任意公约数d 因为d|a , d|q *b ,所以d|(a-qb) 即d|r,因此d也是b,r的公约数,反之成立,估a,b的公约数集合和b a mod b的公约数集合相同,于是他们的最大公约数也相等
int gcd(int a,int b){
return b?gcd(b,a%b):a);
扩展欧几里得