我的最爱——编程，天文，魔方，数学，物理，化学

偶像是牛顿

经过推演，这场战斗你们毫无胜算；

金钱是万能的吗？

数论

1. 位运算(&,|,^,>>,<<,~)

①异或运算的逆运算是它本身，也就是说两次异或同一个数最后结果不变，即

aa \bigoplus⨁ bb \bigoplus⨁ bb=aa。

②取反：二进制补码按位取反，有符号位也会取反。右移就是除以2，左移就是乘2.

③位运算的优先级低于算术运算符（除了取反），而按位与、按位或及异或低于比较运算符

④位运算的应用,位运算一般有三种作用：

(1) 高效地进行某些运算，代替其它低效的方式。

(2) 表示集合。（常用于状压 DP)

(3) 题目本来就要求进行位运算。

判断一个数是不是2的非负整数次幂：

n & (n - 1)== 0;

[Copy](javascript:;)

对2的非负整数次幂取模：

x & (mod - 1);

[Copy](javascript:;)

获取 a 的第 b 位，最低位编号为 0

int getBit(int a, int b) { return (a >> b) & 1; }

[Copy](javascript:;)

将 a 的第 b 位设置为 0 ，最低位编号为 0

int unsetBit(int a, int b) { return a & ~(1 << b); }

[Copy](javascript:;)

2. 快速幂

加速快速幂：根据费马小定理，如果p是一个质数，而整数a不是p的倍数，则有

a^{（p-1）}≡1（mod p）a（p−1）≡1**（modp**）。

3. 扩展欧几里得定理

1. gcd(a,b)=gcd(b,agcd(a,b)=gcd**(b,**a%b)b)
2. 用于解ax+by=cax**+by**=c不定方程的解(a,x,b,y都是整数a,x,b,y都是整数)，根据裴蜀定理，ax+by=cax**+by**=c有解的充分必要条件是cc%gcd(a,b)0gcd(a,b)**0,给出证明，设gcd(a,b)==dgcd**(a,b)==d,则a=nd,b=mda=nd**,b=md**。则ndx+mdy=cndx+mdy=c，化简得d(nx+my)=cd(nx**+my**)=c，则cc一定是dd的倍数，证毕。
3. 实际是先ax+py=gcd(a,b)a∗x+p∗y=gcd(a,b)这个方程后，反推出原方程的解，给解出来的xc/gcd(a,b)x∗c/gcd(a,b)就是ax+by=cax**+by**=c的一个解，那么我们解这个方程首先根据裴蜀定理进行化简，令a=b,b=aa=b,b=a%bb，则该式子是bx+abx**+a%by=gcd(b,aby=gcd(b,a%b)b),由于gcd(b,agcd**(b,a%b)b)=gcd(a,b)=gcd**(a,b),得 bx+abx+a%by=gcd(a,b)by=gcd(a,b)**, 即ay-b(x-a/by)=gcd(a,b)ay−b**(x−a/b∗y)=gcd**(a,b),递归求解到最后，b==0的时候，得到一组解，x=1,y=0x=1,y=0.也就是a1+b0=gcd(a,0)a∗1+b∗0=gcd(a,0),gcd(a,0)gcd(a,0)当然就是aa了.

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

[Copy](javascript:;)

4. 此时得到的xx只是ax+by=gcd(a,b)ax**+by**=gcd(a,b)的一组特解，ax+kab-kab+by=cax**+kab−kab+by**=c,则a(x+kb)+b(y-ka)=ca(x+kb)+b(y−ka**)=c.我们将要求出来的 x,yx**,y 仅仅保证满足 ax + by = 1ax**+by**=1而 xx 不一定是最小正整数解。有可能太大，也有可能是负数
5. 根据特解，x=x*c/gcd(a,b)x=x∗c/gcd(a,b)就得到原方程的一组解。所以如果xx太小，我们就加bb刚好大于等于00，反之减bb。
6. 最小非负整数解：(x**(x%(b/d)+b/d)(b/d)+b/d)%(b/d)(b/d),需注意若a<0a**<0，需改变符号。
7. 显然最小时 d_x=\frac{b}{\gcd(a,b)}dx​=gcd(a,b)b​， d_y=\frac{a}{\gcd(a,b)}dy​=gcd(a,b)a​，在d=\frac{1}{\gcd(a,b)}d=gcd(a,b)1​时取到

那么通解形式就出来了，

x=x_1+sd_x xx=x1​+sdx​x y=y_1-sd_yy=y1​−sdy​ 其中，ss 是任意整数

而且，随着 xx 增大 yy减小 （废话，它们的和一定）

而且，ss 越大，xx 越大，yy越小，反之亦然（重点）

4. 质因数分解

for (int i = 2; i * i <= n; i++)
	{
		if (n % i == 0)
		{
			int cnt = 0;
			while (n % i == 0)
			{
				n /= i;
				cnt++;
			}
			v.push_back((node){i, cnt});
		}
	}
	if (n != 1)
	{
		v.push_back((node){n, 1});
	}

[Copy](javascript:;)

1. 要使得s_i^k \mid m_1^{m_2}sik​∣m1m2​​,则si分解的质因数必须包含m1的所有质因子。

5.线性复杂度解决1~n mod p的逆元(pp为质数)

过程：

1. 令p=ki+rp=ki+r,kk为p/ip/i的商，rr为余数。则k=⌊p/i⌋k=⌊p/i⌋（向下取整）, r=p \ mod\ ir=p mod i.(i<p,k<p,r<ii<p,k<p,r<i)
2. 两边同时乘以i^{-1}r^{-1}i−1∗r−1,得到kr^{-1}+i^{-1}\equiv\ 0 (mod\ p)k∗r−1+i−1≡** 0(mod p)**
3. 移项得i^{-1}\equiv -k*r^{-1}(mod\ p)i−1≡−k∗r−1**(mod p)**
4. 带入刚才得kk和rr的表达式,得到i^{-1}\equiv -⌊p/i⌋*(p \ mod\ i)^{-1}(mod\ p)i−1≡−⌊p/i⌋∗(p mod i)−1**(mod p)**
5. 由于p \ mod\ i<ip mod i<i,所以在求出i^{-1}i−1之前已经求出(p \ mod\ i)^{-1}(p mod** i)−1**
6. 用数组inv[i]记录i^{-1}i−1,则inv[i]=-p/i*inv[p \ mod\ i]\ mod \ p−p**/i∗inv**[p mod i]** mod **p
7. 同时要注意，为了保证i^{-1}>0i−1>0，上式需要两边加上p。
8. 则inv[i]={p-p/i*inv[p \ mod\ i]\ mod \ p}p−p/i∗inv**[p mod i]** mod p
9. 然后可以轻松的由inv[1]=1inv**[1]**=1,在O(1)的时间推出其余答案。
10. 正常可以利用exgcd和快速幂结合费马小定理在log时间解决

6.中国剩余定理

常用来解一元线性同余方程组

一般从这个问题引入，某物品三三数之余二，五五数之余三，七七数之余二。问物几何？

写成方程组的形式就是求解

\left{ \begin{matrix} x\equiv\ 2\ mod\ 3 \ x\equiv\ 3\ mod\ 5 \ x\equiv\ 2\ mod\ 7 \end{matrix} \right.⎩⎨⎧​x≡ 2 mod 3x≡ 3 mod 5x≡ 2 mod 7​

首先，若x_0x0​为原方程的一个解，那么x_0+357*k，k\in 整数x0​+3∗5∗7∗k，k∈整数，也是一个解

解上述方程组其实首先需要解以下3个方程，这里有点线性代数的意思。

\left{ \begin{matrix} x\equiv\ 1\ mod\ 3 \ x\equiv\ 0\ mod\ 5 \ x\equiv\ 0\ mod\ 7 \end{matrix} \right.⎩⎨⎧​x≡ 1 mod 3x≡ 0 mod 5x≡ 0 mod 7​

\left{ \begin{matrix} x\equiv\ 0\ mod\ 3 \ x\equiv\ 1\ mod\ 5 \ x\equiv\ 0\ mod\ 7 \end{matrix} \right.⎩⎨⎧​x≡ 0 mod 3x≡ 1 mod 5x≡ 0 mod 7​

\left{ \begin{matrix} x\equiv\ 0\ mod\ 3 \ x\equiv\ 0\ mod\ 5 \ x\equiv\ 1\ mod\ 7 \end{matrix} \right.⎩⎨⎧​x≡ 0 mod 3x≡ 0 mod 5x≡ 1 mod 7​

记上述三组的解记为

\begin{bmatrix} 1\ 0\ 0\ \end{bmatrix}⎣⎡​100​⎦⎤​

\begin{bmatrix} 0\ 1\ 0\ \end{bmatrix}⎣⎡​010​⎦⎤​

\begin{bmatrix} 0\ 0\ 1\ \end{bmatrix}⎣⎡​001​⎦⎤​

则原方程的解为 22∗\begin{bmatrix} 1\ 0\ 0\ \end{bmatrix}⎣⎡​100​⎦⎤​*+33∗\begin{bmatrix} 0\ 1\ 0\ \end{bmatrix}⎣⎡​010​⎦⎤​*+22∗\begin{bmatrix} 0\ 0\ 1\ \end{bmatrix}⎣⎡​001​⎦⎤​*

问题的关键显然是求上述三组解。 上述三组解是这样求的，先来看第一个。

\left{ \begin{matrix} x\equiv\ 1\ mod\ 3 \ x\equiv\ 0\ mod\ 5 \ x\equiv\ 0\ mod\ 7 \end{matrix} \right.⎩⎨⎧​x≡ 1 mod 3x≡ 0 mod 5x≡ 0 mod 7​

x一定是35的倍数x一定是35的倍数，所以设x=35*yx=35∗y,那么35y\ \equiv\ 1\ mod\ 335y** ≡ 1 mod 3,这里容易求出yy是22**,实际也能看出就是逆元。

求出22以后，x=35*2=70x=35∗2=70，那么第一个方程组的一个特解就出来了。

同理求出其余的两个方程组的特解分别是x=21,x=15x=21,x=15。

则原方程的解为270+321+2*15\ \equiv\ 23\ mod\ 1052∗70+3∗21+2∗15 ≡ 23 mod 105 ，所以这里就求出了23.

因此从这里也能看出线性同余方程组的求解方式，方法就是。

\left{ \begin{matrix} x\equiv\ b_1\ mod\ a_1 \ x\equiv\ b_2\ mod\ a_2 \ …… \ x\equiv\ b_k\ mod\ a_k \ \end{matrix} \right.⎩⎨⎧​x≡ b1​ mod a1​x≡ b2​ mod a2​……x≡** bk​ mod ak​​**

首先还是按照刚才的方式分出多个方程组来，求出每一个的，最后求和。

1. 首先求出N=a_1a_2……a_kN=a1​∗a2​∗*……∗ak​**
2. 对于每一组方程我们按照上面的例题思路来求解，设m=N/a_im=N/ai​,那么紧接着我们需要求出mx\ \equiv\ 1\ mod\ a_imx** ≡ 1 mod ai​,求出这个x以后x**以后。
3. 那么最终这个方程组的解就是mxb_im∗x∗bi​，回想刚才不就是35是m，x求逆元是2，b_i是235是m，x求逆元是2，bi​是2，所以是352235∗2∗2,对应上面的2*702∗70.
4. 然后循环求和，并且求和的时候对NN取余得到答案。

7.扩展中国剩余定理

求解同余方程组

\left{\begin{aligned}x\equiv\ a_1(\mod m_1) \quad\ x\equiv\ a_2(\mod m_2) \quad\ x\equiv\ a_3(\mod m_3) \quad\ ...\quad\x\equiv\ a_k(\mod m_k) \quad\end{aligned}\right.⎩⎨⎧​x≡ a1​(modm1​**)x≡** a2​(modm2​**)x≡** a3​(modm3​**)...x≡ ak​(modmk​**)​​其中m_1,m_2,m_3...m_km1​,m2​,m3​...mk​

为不一定两两互质的整数， 求xx的最小非负整数解.

类似于求多个数字gcdgcd 的方法，先求出前两个的解，然后不停的合并，前两个方程组可以利用扩欧求出最小解，然后循环下去即可。

ll tmp1 = b[1], tmp2 = a[1], ans;
for (int i = 2; i <= n; i++)
{
    ll A, B, C, X, Y;
    C = b[i] - tmp1;
    A = tmp2, B = a[i];
    if (C < 0)
    {
        swap(b[i], tmp1);
        swap(A, B);
    }
    ll g = gcd(A, B);
    C = b[i] - tmp1;
    exgcd(A, B, X, Y);
    X *= C / g, Y *= C / g;
    Y %= A / g;
    if (Y > 0)
    {
        Y -= A / g;
    }
    ans = (b[i] - B * Y) % lcm(a[i], tmp2);
    tmp1 = (b[i] - B * Y) % lcm(a[i], tmp2);
    tmp2 = lcm(a[i], tmp2);
}

[Copy](javascript:;)

8.Lucas定理

定理用于求解大组合数取模的问题，其中模数必须为素数。正常的组合数运算可以通过递推公式求解（详见 排列组合），但当问题规模很大，而模数是一个不大的质数的时候，就不能简单地通过递推求解来得到答案，需要用到 LucasLucas 定理。

公式：C(n,m)\ mod\ p=C(n/p,m/p)C(n%p,m%p)\ mod\ pC(n,m)* mod p=C(n/p,m/p)∗C**(n%p,m%p)** mod **p

递归操作下去，当 m0m0,返回11.也就是C(n,0)1C(n,0)****1

Lucas(n,m)\ mod\ p=Lucas(n/p,m/p)C(n%p,m%p)\ mod\ pLucas*(n,m)** mod p=Lucas**(n/p,m/p)∗C**(n%p,m%p)** mod **p

ll Lucas(ll n, ll m, ll p)
{
    if(m == 0)return 1;
    return C(n % p, m % p, p) * Lucas(n / p, m / p, p) % p;
}

[Copy](javascript:;)

求解C(n%p,m%p)\ mod\ pC(n%p,m%p)** mod **p的时候

当n,mn,m不大的时候，可以预处理出所有的阶乘答案存到数组。数字大的时候可以单独去算。

C(n,m)=n!/(n-m)!m!C(n,m)=n!/(n−m*)!∗m**!也就是(n*(n-1)……(n-m+1))/m!\ mod\ p**(n∗**(n−1)∗……∗(n−m+1))/m! mod p 分子分母都可以直接计算，牵扯到除法因此需要求m!*x\equiv\ 1\ mod\ pm!∗x≡ 1 mod p求出这个xx,也就是逆元，由于pp是质数，因此用费马小定理求解即可。

ll quick_pow(ll a, ll b, ll mod)
{
    ll ans = 1;
    while (b)
    {
        if (b & 1)
        {
            ans *= a;
            ans %= mod;
        }
        a *= a;
        a %= mod;
        b >>= 1;
    }
    return ans;
}
ll inv(ll a, ll p) //求a mod p下的逆元。
{
    return quick_pow(a, p - 2, p);
}
ll C(ll n, ll m, ll p)
{
    if (m > n)
        return 0;
    ll up = 1, down = 1;
    for (int i = n - m + 1; i <= n; i++)
        up = up * i % p;
    for (int i = 1; i <= m; i++)
        down = down * i % p;
    return up * inv(down, p) % p;
}