本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-08-02 20:22:34

二项式定理

mx没学这个，看了pry的题解，了解了一下。

$$(x+y)^n=C^0_n x^ny^0+C^1_n x^{n-1}y^1+C^2_n x^{n-2}y^2+\dots+C^{n-1}_n x^{1}y^{n-1}+C^n_n x^{0}y^n$$

进一步简化：

$$(x+y)^n= \sum^{n}_{k=0} C^k_n x^{n-k}y^k$$

Exgcd

用来求解线性同余方程（$ax+by=\gcd(a,b)$）的一组可行解。

$$设 ax_1+by_1=\gcd(a,b) , bx_2+(a \ \bmod \ b)y_2=\gcd(b,a \bmod b)$$

$$\because \gcd(a,b)= \gcd(b,a \bmod b)$$

$$\therefore ax_1+by_1=bx_2+(a \ \bmod \ b)y_2$$

$$\because a \bmod b=a-b \times \left \lfloor \frac{a}{b} \right \rfloor $$

$$\therefore ax_1+by_1=bx_2+(a-b \times \left \lfloor \frac{a}{b} \right \rfloor)y_2$$

$$\therefore ax_1+by_1=bx_2+ay_2-b(y_2 \times \left \lfloor \frac{a}{b} \right \rfloor) $$

$$\therefore ax_1+by_1=ay_2+b(x_2-y_2 \times \left \lfloor \frac{a}{b} \right \rfloor) $$

$$\therefore x1=y2,y1=x_2-y_2 \times \left \lfloor \frac{a}{b} \right \rfloor$$

代码

int exgcd(int a,int b,int &x,int &y){
    if(b==0){
        x=1,y=0;
        return a;
    }
    d=exgcd(b,a%b,x,y);
    
    int xx=x;
    x=y;
    y=xx-(a\/b)*y;
    return d;
}