数论

最大公约数 ( \(gcd(a,b)\) )

由欧几里得定理可知gcd(b,a mod b)

ll gcd(ll a,ll b)
{
    if(b == 0) return a;
    else return gcd(b,a%b);
}

顺便得出两数的最小公倍数

ll lcm(ll a,ll b)
{
    return (a/gcd(a,b))*b;
}

多个数时，求任意两个的最大公约数和最小公倍数，用这两个数再继续结合剩余的数求最大公约数和最小公倍数，最后的结果就是多个数的最大公约数和最小公倍数了

欧拉函数

定义：表示的是小于等于n和n互质的数的个数。记作\(\varphi(n)\)

思路：先假设答案为n，分解质因数，如果这个质因数为x，那么这个答案就变成了\((x-1)/x\)倍（因为少了质因数那一部分\(1/x\)）

代码：

ll f_ol(ll x)
{
	ll ans = x;
	for(int i = 2;i*i <= x;i++)
	{
		if(x%i==0)
		{
			ans = ans/i*(i-1);
			while(x%i==0) x/=i;
		}
	}
	if(x>1) ans = ans/x*(x-1);
	return ans;
}

莫比乌斯反演

赛瓦维斯特定理

已知\(a,b\)为大于1的正整数,\(gcd(a,b)=1\),则使不定方程\(ax+by=C\)不存在非负整数解的最大整数\(C=a×b−a−b\)

0_{a中间是空的，加上一个b后0}a中有了一个数，以此类推要填满需要(a-1)个b，所以(a-1)b后的数都被填上了，而(a-1)b之前的(a-1)b-a不存在所以\(C=a×b−a−b\)

扩展欧几里得

作用：求\(ax+by=gcd(a,b)\)的可行解

设\(x',y'\)满足\(bx'+(a\ mod\ b)y'=gcd(b,a\ mod\ b)\)
又\(a\ mod\ b=a-\lfloor\frac{a}{b}\rfloor *b\)，\(gcd(a,b)=gcd(b,a\ mod\ b)\)
可得\(ax+by=bx'+(a-\lfloor\frac{a}{b}\rfloor *b)y'\)
即\(ax+by=ay'+b(x'- \lfloor\frac{a}{b}\rfloor *b*y')\)
即\(x=y',y=x'- \lfloor\frac{a}{b}\rfloor *b*y'\)
最后b肯定为0，此时\(ax=a\)所以赋值\(x=1,y=0\)再递归回去

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

逆元

费马小定理

若p为素数，gcd(a,p) = 1，则

\[a^{p-1} \equiv 1\pmod p \]

所以

\[a*a^{p-2} \equiv 1\pmod{p} \]

即\(a^{p-2}\)是a的逆元，而\(a^{p-2}\)可以用快速幂来求

ll  qpow(ll a,ll b)//b = p - 2
{
    ll ans = 1;
    a = (a % p + p) % p;
    for(;b;b >>= 1)
    {
        if(b&1) ans = (a*ans)%p;
        a=(a*a)%p;
    }
    return ans;
}

线性逆元

首先1的逆元为1
\(a^{-1}\equiv-\lfloor{\frac{p}{a}}\rfloor(p\ mod\ a)^{-1}\)

ll ny[MAXN];
void pre_ny()
{
    ny[1] = 1;
    for(int i = 2;i <= n;i++){
        ny[i] = (ll)(p - p / i)*ny[p % i] % p;//p - p / i是为了防止负数 
    }
}

等比数列求和公式

ll sum_mul(ll a1,ll n,ll q)//q > 1时
{
	return ((((qpow(q,n) + p - 1) % p) * fmx(q - 1) % p) * a1) % p;
}

组合数

阶乘逆元

ll jcny[MAXN];
void pre_jcny()
{
    jcny[0] = jcny[1] = 1;
    for(int i = 2;i <= n;i++){
        jcny[i] = (jcny[i - 1] * ny[i]) % p;
    }
}

阶乘

ll jc[MAXN];
void pre_jc()
{
    jc[1] = 1;
    for(int i = 2;i <= n;i++){
        jc[i] = (jc[i - 1] * i) % p;
    }
}

组合数

\(C_{n}^{m}={\frac{n!}{m!(n-m)!}}\)

\(C_{n}^{m}={n!(m!)^{-1}((n-m)!)^{-1}\pmod{p}}\)

ll C(ll n,ll m)
{
	return ((jc[n]*jcny[m])%p)*jcny[n-m])%p;
}

中国剩余定理

用于计算以下形式的同余方程(所有数互素时)

\[\begin{cases} x\equiv{a_1}\pmod{n_1} \\ x\equiv{a_2}\pmod{n_2} \\ \vdots\\ x\equiv{a_k}\pmod{n_k} \end{cases} \]

过程：

1.计算所有模数的积n
2.计算\(m_i=\frac{n}{n_i}\)
3.计算\(m_i^{-1}\pmod{n_i}\)
4.计算\(c_i=m_im_i^{-1}\)（不取模）
5.\(x\)=求和\(c_i*a_i\)

int ci[MAXN],ni[MAXN];
ll CRT(int cnt)
{
    ll n = 1,ans = 0;
    for(int i = 1;i <= cnt;i++) n*=ni[i];
    for(int i = 1;i <= cnt;i++)
    {
        ll m = n / ni[i],mm,t;
        exgcd(m,ni[i],mm,t);
        ans = (ans + ci[i]*mm*m%n)%n;
    }
    return (ans%n + n) % n;
}

拓展中国剩余定理

中国剩余定理考虑了所有数互质的情况，那么如果不互质，结果为多少呢？

\[\begin{cases} x\equiv{a_1}\pmod{n_1} \\ x\equiv{a_2}\pmod{n_2} \\ \end{cases} \]

解方程

\[\begin{cases} x={a_1}+{n_1}*{t_1} \\ x={a_2}+{n_2}*{t_2} \\ \end{cases} \]

\[a_1-a_2=n_1*t_1-n_2*t_2 \]
如果\(a_1-a_2\)为\(gcd(n_1,n_2)\)的整数倍，则有解，通过拓展欧几里得求解，然后乘上倍数，在返回带回原来的式子，得到\(x\equiv{a_1+n_1*t_1}\pmod{lcm(n_1,n_2)}\)

ll a1 = a[1],n1 = n[1];
bool flag = true;
for(int i = 2;i <= m;i++)
{
	ll a2 = a[i],n2 = n[i],t1,t2;
    exgcd(n1,n2,t1,t2);
    if((a1-a2)%gc!=0)
        flag = false;
    t1 = t1*(a1-a2)/gc;
    x = (n1*t1+x);
    n1 = n1/gc*n2;
    t1 = (t1%n1+n1)%n1;
}