GCD

int do_gcd(int p,int q){
	if(!q)return p;
	else return do_gcd(q,p%q);
}

Time: \(O(logn)\)

• 有一个定理：\(lcm(a,b)*gcd(a,b)=a*b\)，求完gcd后可以Time:\(O(1)\)求lcm

---

Ex_GCD (恶心gcd)

过程

由裴蜀定理得 \(ax+by=c\) ，当c是gcd(a,b)的倍数的时候，才能有解

那么从基础的地方开始：如何求 \(ax+by=gcd(a,b)\) ？ 因为解决完这个问题后， 答案再乘上 \(a/\gcd(a,b)\) 就行了

解法:（来源于oi-wiki )

\(a x_{1}+b y_{1}=\operatorname{gcd}(a, b)\)

\(b x_{2}+(a \bmod b) y_{2}=\operatorname{gcd}(b, a \bmod b)\)

由欧几里得定理可知: \(\quad \operatorname{gcd}(a, b)=\operatorname{gcd}(b, a \bmod b)\)

所以 \(a x_{1}+b y_{1}=b x_{2}+(a \bmod b) y_{2}\)

又因为 \(a \bmod b=a-\left(\left\lfloor\frac{a}{b}\right\rfloor \times b\right)\)

所以 \(a x_{1}+b y_{1}=b x_{2}+\left(a-\left(\left\lfloor\frac{a}{b}\right\rfloor \times b\right)\right) y_{2}\)

\(a x_{1}+b y_{1}=a y_{2}+b x_{2}-\left\lfloor\frac{a}{b}\right\rfloor \times b y_{2}=a y_{2}+b\left(x_{2}-\left\lfloor\frac{a}{b}\right\rfloor y_{2}\right)\)

因为 \(a=a, b=b,\) 所以 \(x_{1}=y_{2}, y_{1}=x_{2}-\left\lfloor\frac{a}{b}\right\rfloor y_{2}\)

将 \(x_{2}, y_{2}\) 不断代入递归求解直至 gcd （最大公约数, 下同) 为 \(0\) 递归 \(x=1, y=0\) 回去求解。

• 结论：两个式子可以得出 \(x_{1}=y_{2}, y_{1}=x_{2}-\left\lfloor\frac{a}{b}\right\rfloor y_{2}\) 直到\(x=1,y=0\)时返回0

代码

void exgcd(int p,int q,int &x,int &y){
	if(!q){x=1,y=0;return ;}
    exgcd(q,p%q,x,y);
    int tmp=x;
    x=y,y=tmp-(p/q)*y;
    return z;
}

Time:\(O(logn)\) ( 因为p和q和gcd复杂度是一样的，而终止条件也是p=0 )

用递归做可以让常数稍微减少，但问题不大就懒得写了qwq