辗转相除法更相减损法,辗转相除法和更相减损法举例

时间复杂度

o(n)

题目代码 int gcd(int a,int b){ if(a==b)return a; return a>b?gcd(a-b,b):gcd(b-a,a);} 特殊情况

辗转相除法可以用来求若干个形如（p/q）^ri的数的最大公约数，其中：
——p/q不可以再表示为次幂的形式
​——p、q、ri均为正整数

算法推导

求指数的最大公约数，即：

f(p^x , p^y) = p(x,y) = p(y,x-y) = f(p^y,p(x-y)) = f(p^y, p^x / p^y)

X要大于Y

特殊情况下的代码 LL gcd_sub(LL a,LL b){ if(b>a)swap(a,b); if(b==1)return a; return gcd_sub(b,a/b);}