数论

同余

​ 若$a\equiv b(mod\ m)$， $a\equiv b(mod\ n)$ 则 $a\equiv b(mod\ (n,m))$

​ 若$(k, m) = d$，$ka \equiv kb(mod\ m)$，则 $a \equiv b(mod\ \frac{m}{d})$

简化剩余系

所有$n$满足$0<n\leq m, (n,m)=1$ 构成了一个模$m$的简化剩余系

记这样的$n$的个数为$\varphi(m)$

$\varphi(m)=m\prod_{p|m}(1-\frac{1}{p})$

ll eular(ll n)//求单个数
{
    ll ans = n;
    for(int i=2; i*i <= n; ++i)
    {
        if(n%i == 0)
        {
            ans = ans/i*(i-1);
            while(n%i == 0)
                n/=i;
        }
    }
    if(n > 1) ans = ans/n*(n-1);
    return ans;
}

int m[n],phi[n],p[n],nump;
//m[i]标记i是否为素数;p是存放素数的数组;nump是当前素数个数;phi[i]为欧拉函数
void eular()
{
    phi[1]=1;
    for (int i=2;i<=n;i++)
    {
        if (!m[i])//i为素数
        {
            p[++nump]=i;//将i加入素数数组p中
            phi[i]=i-1;//因为i是素数,由特性得知    
        }    
        for (int j=1;j<=nump&&p[j]*i<=n;j++)  //用当前已得到的素数数组p筛,筛去p[j]*i
        {
            m[p[j]*i]=1;//可以确定i*p[j]不是素数 
            if (i%p[j]==0) //看p[j]是否是i的约数,因为素数p[j],等于判断i和p[j]是否互质 
            {
                phi[p[j]*i]=phi[i]*p[j]; //特性2
                break;
            }
            else phi[p[j]*i]=phi[i]*(p[j]-1); //互质,特性3其,p[j]-1就是phi[p[j]]   
        }
    }
}

费马小定理

欧拉定理

若$(a,m)=1$，则$a^{\varphi(m)} \equiv 1(mod\ m)$

特殊的，若$m$为质数，则$\varphi(m)=m-1$，$a^{m-1}\equiv1(mod\ m)$（费马小定理）

逆元

$O(n)$求$1\thicksim n$的逆元 :

​ $inv[i]=(p-\frac{p}{i})*inv[p\ mod\ i] mod\ p$

裴蜀定理

对于不定方程 $ax + by = m$, 则其有整数解的充要条件为$gcd(a, b) | m$

对于$\forall x, y \in Z$

函数$f(x,y) = ax + by$的最小正整数取值为 $f(x, y) = gcd(x, y)$

扩展欧几里得

可求出 $ax + by = gcd(a,b)$的一组解

通项 : $a*(x + k * \frac{b}{gcd(a,b)}) + b * (y + (-k) * \frac{a}{gcd(a,b)}) = gcd(a,b)$

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

$exgcd$ 最终返回 $gcd(a,b)$

解线性同余方程

$ax\equiv n(mod \ b)$

$a,b,n$ 为给定的整数，$x$ 为未知数，需要从区间 $[0,n-1]$ 中求解 $x$

若 $gcd(a,b)$ 不可整除 $n$ ，则方程无解

扩展欧几里得求解: 将 $ax\equiv n(mod \ b)$ 等价成 $ax+by=n$ ，其中 $x,y$ 为未知数

对于 $ax+by=n$ 先求出一组解 $x_0,y_0$，即 $ax_0+by_0=gcd(a,b)$

那么就得到方程 $a\frac{n}{gcd(a,b)}x_0+b\frac{n}{gcd(a,b)}y_0=n$，$\frac{n}{gcd(a,b)}x_0$ 和 $\frac{n}{gcd(a,b)}y_0$ 是原方程的一组解

最小整数解为 $(x_0 \ mod \ t + t) \ mod \ t$，其中 $t = \frac{b}{gcd(a,b)}$

中国剩余定理（CRT）

解线性同余方程组

只可求解模数两两互质

ll n, a[20], m[20];

ll qmul(ll a, ll b, ll mod)	//快速乘， 防止爆ll
{
    ll ans = 0;
    while (b > 0)
    {
        if (b & 1)
            ans = (ans + a) % mod;
        a = (a + a) % mod;
        b >>= 1;
    }
    return ans;
}

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

ll crt()
{
    ll ans = 0, M = 1;
    for (int i = 1; i <= n; i++)
        M *= m[i];
    for (int i = 1; i <= n; i++)
    {
        ll x, y;
        ll Mi = M / m[i];
        exgcd(Mi, m[i], x, y);			//处理后x即为Mi的逆元
        x = (x % m[i] + m[i]) % m[i];	//防止x为负数
        ans = (ans + qmul(qmul(Mi, a[i], M), x, M)) % M; //模M得到唯一解
    }
    return (ans + M) % M;
}

void solve()
{
    cin >> n;
    for (ll i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i++)
        cin >> m[i];
    for (int i = 1; i <= n; i++)
        a[i] = (a[i] % m[i] + m[i]) % m[i]; //a[i]可能为负数，需要预处理
    cout << crt();
}

excrt

增量法（excrt），可以处理任意模数，但$lcm(所有模数)$要在不能爆数据类型

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

void merge(ll& a, ll& b, ll c, ll d)
{
    ll x, y;
    ll g = exgcd(b, d, x, y);
    if ((c - a) % g != 0)
    {
        a = b = -1;
        return;
    }
    d /= g;
    ll t0 = ((c - a) / g) % d * x % d;
    if (t0 < 0)
        t0 += d;
    a = b * t0 + a;
    b = b * d;
}

void solve()
{
    int n;
    cin >> n;
    ll a = 0, b = 1;//x mod b = a
    for (int i = 1; i <= n; i++)
    {
        int c, d;//x mod d = c 
        cin >> d >> c;
        merge(a, b, c, d);
    }
    cout << a << '\n';
}

将合数的问题变为素数幂的问题

给定 $n$ 个方程，$x\equiv a_i\ (mod\ m_i)$ ，判断方程是否有解

模一个数 和 模这个数的所有素数幂等价

可以将每个$m_i$转化为素数幂的形式，如$x \equiv 3(mod\ 12)$可以转化为

​ $x \equiv 4(mod\ 3)$

​ $x \equiv 0(mod\ 3)$

（同时满足）

方程组有解则说明原式有解

若存在同一素数的多种幂次，则解$x$时只需考虑最高幂次（但仍需检验其它幂次的正确性）

void solve()
{
    map<ll, vector<pair<int, int>>> mp;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        ll a;
        cin >> a >> m;
        for (int j = 2; j * j <= m; j++)
        {
            if (m % j == 0)
            {
                ll p = j, pe = 1; //pe为素数幂
                while (m % j == 0)
                    m /= j, pe *= j;
                mp[p].push_back({ pe, a % pe }); //放入素数幂和取余后的结果
            }
        }
        if (m != 1)
            mp[m].push_back({ m, a % m });
    }
    for (auto x : mp)
    {
        auto e = x.second;
        ll v = max_element(all(e))->second; //找到最高次幂
        for (auto i : e)
        {
            if (v % i.first != i.second)	//检验低幂次的正确性，若结果不同说明无解
            {
                cout << "No" << endl;
                return;
            }
        }
    }
    cout << "Yes" << endl;
}

扩展Lusca定理

int m, T, M, phipe;
pair<int, int> x[110];
ll pr[110];
ll ans[N], a[N], b[N], fac[1010000];

ll qpowmod(ll base, ll pow, ll mod)
{
	base %= mod;
	ll ans = 1;
	while (pow)
	{
		if (pow & 1)
			ans = ans * base % mod;
		pow >>= 1;
		base = base * base % mod;
	}
	return ans;
}

ll cntp, cnts;
ll cal(ll a, int p, int pe, int w)//分解阶乘（将p从阶乘中分解出来）
{
	ll val = 1;
	while (a)
	{
		cntp += (a / p) * w;
		cnts += (a / pe) * w;
		val = val * fac[a % pe] % pe;
		a /= p;
	}
	return val;
}

ll C(ll a, ll b, int p, int pe)
{
	cntp = cnts = 0;
	ll f1 = cal(a, p, pe, 1);//f1,f2,f3为每次剩下的乘积
	ll f2 = cal(b, p, pe, -1);
	ll f3 = cal(a - b, p, pe, -1);
	ll v1 = f1 * qpowmod(f2 * f3 % pe, phipe - 1, pe) % pe;
	ll v2 = qpowmod(p, cntp, pe);//p
	ll v3 = qpowmod(fac[pe], cnts, pe);//整组的
	return v1 * v2 % pe * v3 % pe;
}

void solve()//T组测试样例，模数相同
{
	cin >> m >> T;
	M = m;
	int tot = 0;
	for (int i = 2; i <= m; i++)//分解质数， 若m较大， 则 i * i <= m, 最后再判if(m > 1)
	{
		if (m % i == 0)
		{
			int p = i, pe = 1;
			while (m % i == 0)
			{
				m /= i;
				pe *= i;
			}
			x[++tot] = { p, pe };
		}
	}

	for (int i = 1; i <= tot; i++)//CRT
	{
		int pe = x[i].second;
        ll Mi = M / pe;
		for (int c = Mi; c < M; c += Mi)//也可以用exgcd求
		{
			if (c % pe == 1)
			{
				pr[i] = c;
				break;
			}
		}
	}

	for (int i = 1; i <= T; i++)
		cin >> a[i] >> b[i];
	for (int i = 1; i <= tot; i++)
	{
		int p = x[i].first, pe = x[i].second;
		fac[0] = 1;
		for (int j = 1; j <= pe; j++)
		{
			if (j % p == 0)
				fac[j] = fac[j - 1];
			else
				fac[j] = fac[j - 1] * j % pe;
		}
		phipe = pe / p * (p - 1);//用于后面求逆元
		for (int j = 1; j <= T; j++)
			ans[j] = (ans[j] + C(a[j], b[j], p, pe) * pr[i] % M) % M;
	}
	for (int i = 1; i <= T; i++)
		cout << ans[i] << '\n';
}