8.2 mx 数论记录

· · 个人记录

二项式定理

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;
}