ProgramAlgTrain/20240828/一本通/learn.md

数学问题

整数的性质

问题	答案
带余除法又称	欧几里德除法
正整数n的表示方法	n=2^ml(m\in N,l\in \{ l \mod 2 = 1\})
常见的整数判定方法(X)	1. 末位可被2 or 5整除，X就可 2. 末两位可被4 or 25，X即可 3. 末三位可被8 or 125整除，X就可 4. (奇数位之和-偶数位上的数字之和)%11==0，这个数就可 5. (末三位之前的数-末三位的数)%(7 or 11 or 13)==0，就可 6. 从后往前两个数组成一个两位数求和%99==0，那么就可
余数判别方法使用用途	快速求出大数字余数
同余符号写法，写出a同余于b模m	a\equiv b (\mod m)
快速幂板子	...
埃氏筛	...
质因数分解	从小到大即可
x与y的最大公因数m和最小公倍数n之间的关系	x y=mn

快速幂

int binExp(int b,int e,int m){
    int r = 1;
    while(e>0){
        if(e%2==1){
            r = (r*b)%m;
        }
        b = b*b %m;
        e = e>>1;
    }
    return r;
}

排列组合

问题	答案
两个基本原理	1.两个步骤之间没有关联用加法 2.两个步骤之间没有关联用乘法
排列公式	A^m_n={n!\over(n-m)!}
组合公式	C^m_n={n!\over m!(n-m)!}=A^m_n{1\over m!}=C^{n-m}_n
0!=?	0!=1