关于约数的算法

欧几里得算法-gcd

gcd(a,b)=gcd(b,a%b),其中a为整数,b是不为0的整数.

证明:

如果a<b,a%b=a,明显有,gcd(a,b)=gcd(b,a).

如果a>=b,设a=k*b+r.设d为a,b的任意公因数,因为d|a,d|b,所以d|(a-k*b),因此d也是b和a%b的公因数,反过来亦成立,因此a和b公因数集合和b和a%b的公因数集合相同,a和b的最大公因数即为b和a%b的最大公因数.

作用:求最大公约数

实现:

1 int gcd(int a,int b)
2 {
3     return b?gcd(b,a%b):a;
4 }

复杂度:O(log(a+b))

扩展欧几里得算法-exgcd

作用:求整数解x和y使得ax+by=gcd(a,b)

原理:

给出方程ax+by=gcd(a,b)(这里假设b不为0),由公式可知有b*x1+a%b*y1=gcd(b,a%b).a%b可表示为a-a/b*b(这里的除是整除后向下取整),因此有:

1:ax+by=gcd(a,b)

2:b*x1+(a-a/b*b)*y1=gcd(b,a%b)

由gcd性质可知gcd(a,b)=gcd(b,a%b),因此有:

ax+by=b*x1+(a-a/b*b)*y1

把等式右边化简一下有:

ax+by=a*y1+b*(x1-a/b*y1)

因此有:

x=y1

y=x1-a/b*y1

这样不断递归求解下去,当递归到b为0时,x=1,y=0,再回溯一遍就能得到原方程的解了.当然扩展欧几里得在实现的过程中也能求出gcd(a,b).

 1 int exgcd(int a,int b,int &x,int &y)
 2 {
 3     if(!b)
 4     {
 5         x=1,y=0;
 6         return a;
 7     }
 8     int g=exgcd(b,a%b,y,x); //简化写法
 9     y-=a/b*x; //y从下一个方程回溯回来时是下一个方程的x
10     return g;
11 }

复杂度:O(log(a+b))

扩展:事实上ax+by=gcd(a,b)的解有穷多个,而exgcd求出来的解只是其中一个特解.假设exgcd求出x0和y0,则方程解集为x=x0+k(b/gcd(a,b)),y=y0-k(a/gcd(a,b)).把解集代入方程就能知道理由了.若要求ax+by=c的解x,y,先看gcd(a,b)能否整除c,如果不能整除的话此方程无解.如果能整除的话只需要把x0,y0扩大c/gcd(a,b)倍即可得到一个特解,然后把这个特解套入上面公式即可得出解集.

关于约数的算法

原文：https://www.cnblogs.com/VBEL/p/11431491.html