数学基础

· · 个人记录

数学基础

1.基本定理

2.同余

运算

加减：直接算。

乘：直接乘，但是可能会导致同余弱化。

除：不能直接除，但如果 ka\equiv kb(mod\ m),\gcd(k,m)=1，那么 a\equiv b(mod\ m)

完系与缩系

完系：m 个剩余类每个取一个代表元，m 的一个完系是 0\sim m-1。

缩系（简化剩余系）：与 m 互质的等价类中取一个代表元，如 6 的一个缩系是 1,5， 7 的一个缩系是 1,2,3,4,5,6。

欧拉函数与欧拉定理

欧拉函数：定义 \varphi(m) 为模 m 意义下缩系大小，显然有 \varphi(m)=m-1(m\in prime)。

欧拉函数求法：若 m=\prod_{i=1}^na_i^{p_i}，则 \varphi(m)=m\prod_{i=1}^n1-\frac 1 {p_i}=\prod_{i=1}^n(p_i-1)p_i^{a_i-1}。

定理：\sum_{d\mid m}\varphi(d)=m

引理：若 a_1,a_2,\dots,a_{\varphi(m)} 是缩系且 \gcd(k,m)=1，那么 ka_1,ka_2,\dots ,ka_{\varphi(m)} 也是缩系。

证明：假设变换后不是缩系，那么 \exists 1\leq i<j\leq \varphi(m),ka_i\equiv ka_j(mod\ m)

因为 \gcd(k,m)=1，所以 a_i\equiv a_j(mod\ m)。根据缩系定义，这不可能出现，所以矛盾。

得证。

欧拉定理：若 \gcd(k,m)=1，则 k^{\varphi(m)}\equiv 1(mod\ m)。

证明：设模 m 意义下一个缩系为 a_1,a_2,\dots ,a_{\varphi(m)}，那么 ka_1,ka_2,\dots,ka_{\varphi(m)} 也是缩系。

由于缩系中每个元素模 m 后分别对应一个与 m 互质的剩余类，而互质剩余类不会改变，所以对两个缩系做连乘，有 k^{\varphi(m)}\prod_{i=1}^{\varphi(m)}a_i\equiv \prod_{i=1}^{\varphi(m)}a_i(mod\ m)。

根据定义，显然 \gcd(\prod_{i=1}^{\varphi(m)}a_i,m)=1，由同余除法性质可得 k^{\varphi(m)}\equiv 1(mod\ m)。

得证。

推论：对于任意 k,m，有 k^m\equiv k^{m-\varphi(m)}(mod\ m)。

费马小定理

费马小定理：若 p\in prime，则 a^{p-1}\equiv 1(mod\ p)。

证明：p\in prime，则 \varphi(p)=p-1，代入欧拉定理得证。

这个定理最常用来求逆元，因为模数一般是质数，那么 a^{p-2}·a\equiv 1(mod\ p)，因此 a^{p-2} 就是a 在模 p 意义下的逆元。

阶

高次同余方程的阶：最小的正整数 d 使得 a^d\equiv 1(mod\ m)，则 d 为 a 对 m 的阶。由欧拉定理易得阶的存在性。

定理：若 a^x\equiv 1(mod\ m)，则 d\mid x。

证明：显然 a^{x\%d}\equiv 1(mod\ m)，若 x\%d 不为 0 则违反了 d 的最小性，矛盾。

得证。

原根和指数

原根：若 x 对 m 的阶为 \varphi(m)，则称 x 为 m 的原根。

性质：对于任意一个原根 x，x,x^2,x^3,\dots ,x^{\varphi(m)} 是模 m 意义下的一个缩系。

证明：假设不是缩系，因为 \gcd(x,m)=1，所以所有数都是缩系中的数，这样如果不是缩系则 \exists 1\leq i<j\leq \varphi(m),x^i\equiv x^j(mod\ m)。

两边做除法得 x^{j-i}\equiv 1(mod\ m)。

因为 j-i<\varphi(m)，矛盾。

得证。

定理：1,2,4,p^k,2p^k(p\in \complement_{prime}{\{2\}},k\in \mathbb{N_+}) 是所有有原根的数。

证明：不会。

由这个定理可以得到素数都有原根。

原根的求法：记最小的原根为 g，大约不超过 O(n^{\frac14})，暴力找出来，则所有 g^k(\gcd(k,\varphi(m)=1) 都是原根。

通过这种求法容易得到原根共有 \varphi(\varphi(m)) 个。

指数：若 p\in prime，a 是 p 的原根且 a^k\equiv b(mod\ m)(k\leq m-1)，则称 k 为 b 的指数，记作 \mathrm{ind}_ab。通过指数可以把模意义乘法变成指数加法。

一次同余方程

求 ax+b\equiv 0(mod\ m) 的正整数解。

这东西其实就是 ax+b=my，转换成上面的裴蜀定理，不再赘述。

中国剩余定理

m=\gcd(m_1,m_2)，则方程组 x\equiv a_1(mod\ m_1) 和 x\equiv a_2(mod\ m_2) 有解的充要条件是 m\mid a_1-a_2，且 x 模 m 有唯一解。

显然当 \gcd(m_1,m_2)=1 时方程组恒有解。

继续推广，得到对于一组 m_1,m_2,\dots,m_n，若 \forall 1\leq i<j\leq n,\gcd(m_i,m_j)=1，那么方程组 x\equiv a_i(mod\ m_i)(i\in[1,n]\cup\mathbb{N_+}) 在模 \prod_{i=1}^nm_i 意义下有唯一解。

我们考虑求出这个解。令 M_i=\frac{\prod_{j=1}^nm_j}{m_i}，b_i 满足 b_iM_i\equiv 1(mod\ m_i)，则解为 \sum_{i=1}^na_ib_iM_i。正确性显然，分别考虑对于模 m_1 到 m_n 的余数即可。

3.二次同余方程

第一型佩尔方程

形如 x^2-Dy^2=1(x,y,D\in\mathbb{N_+}) 的方程称为第一型佩尔方程。

定理1：第一型佩尔方程在 \sqrt D\in\mathbb{N_+} 时无正整数解，否则有无穷多组正整数解。

证明：显然 x^2 是完全平方数，Dy^2=x^2-1 不是完全平方数，而 y^2 是完全平方数，因此若有正整数解 D 一定不能是完全平方数。

定理2：若最小解为 x_0,y_0，那么任意一个解 x_n,y_n 满足 x_n+\sqrt Dy_n=(x_0+\sqrt Dy_0)^{n+1}，由此得到递推式 x_n+\sqrt Dy_n=(x_{n-1}+\sqrt Dy_{n-1})(x_0+\sqrt Dy_0)。

证明：还是不会。

实际应用中 D 一般不会太大，可以先暴力算出 x_0,y_0，然后利用递推式直接求解（直接用通项会掉精度）。

例如 x^2-2y^2=1，很容易算出 x_0=3,y_0=2，那么 x_1+\sqrt2y_1=(3+2\sqrt2)^2=17+12\sqrt2，因此 x_1=17,y_1=12。

第二型佩尔方程

形如 x^2-Dy^2=-1(x,y,D\in\mathbb{N_+}) 的方程称为第二型佩尔方程。

同样的，在 \sqrt D\in\mathbb{N_+} 时无解，否则有无穷多解。

找到最小解 x_0,y_0，一组解 x_n,y_n 满足 x_n+\sqrt Dy_n=(x_0+\sqrt Dy_0)^{2n+1}，递推式 x_n+\sqrt Dy_n=(x_{n-1}+\sqrt Dy_{n-1})(x_0+\sqrt Dy_0)^2。

例题：给定 T，求使 n(n+1)=2m(m+1) 有正整数解的大于 T 的最小 n。

n^2+n=2m^2+2m 4n^2+4n=8m^2+8m (2n+1)^2=2(2m+1)^2-1 (2n+1)^2-2(2m+1)^2=-1

令 x=2n+1,y=2m+1

x^2-2y^2=-1

手算 x_0,y_0，暴力递推，因为增长是指数的所以可以过，也可以矩阵快速幂倍增。

勾股方程

勾股方程的通解是 $x=2kuv,y=k(u^2-v^2),z=k(u^2+v^2)$，其中 $u,v,k\in\mathbb{N_+},u>v,\gcd(u,v)=1$。 证明：显然 $k$ 可以最后放缩，我们只要证明对于 $\gcd(x,y,z)=1$ 时，满足 $x=2uv,y=u^2-v^2,z=u^2+v^2

根据加法的奇偶性，x,y,z 必然是两奇一偶。

同时 z 一定是奇数，因为如果 z 是偶数，那么 z^2\equiv 0(mod\ 4)，而左边两奇数 x^2\equiv y^2\equiv 1(mod\ 4)，x^2+y^2\equiv 2(mod\ 4)，两边不可能相等。

移项，得到 $x^2=(z+y)(z-y)$，显然 $\gcd(y,z)=1$，否则 $x,y,z$ 不互质。那么 $\gcd(z+y,z)=1$。因为 $z+y$ 是奇数，所以 $\gcd(z+y,2z)=1$。辗转相除一次，得到 $\gcd(z+y,z-y)=1$。 两个互质的数乘起来是完全平方数，那么必须分别是完全平方数，所以有 $z+y=u^2,z-y=v^2$，解得 $x=uv,y=\frac{u^2-v^2}2,z=\frac{u^2+v^2}2$。 得证。 这样构造出的勾股方程的解满足 $\gcd(x,y,z)=k$。 勾股方程通解可以优化枚举勾股数的效率。 ## 4.排列组合 ### 勒让德定理 $p\in prime$，则 $n!$ 质因数分解中 $p$ 的次数是 $\sum_{i=1}\lfloor\frac{n}{p^i}\rfloor=\frac{n-S(n)}{p-1}$，$S(n)$ 表示 $p$ 进制下 $n$ 的数位和。 推论：$\dbinom {n+m}m$ 中 $p$ 的幂次等于 $n+m$ 在 $p$ 进制下进位次数。 ### 卢卡斯定理 若 $p$ 进制下 $n$ 表示为 $(a_0a_1\dots a_m)$，$k$ 表示为 $(b_0b_1\dots b_m)$（允许前导 0），那么 $\dbinom n k\equiv\prod_{i=0}^m\dbinom{a_i}{b_i}(mod\ p)

这个定理用于计算大组合数取模。

例题：【模板】卢卡斯定理

直接应用结论即可。

#include<iostream>
#include<cstdio>
using namespace std;
#define int long long
int t,n,m,p,fac[200001],inv[200001];
inline int pw(int a,int b)
{
    int res=1;
    while(b)
    {
        if(b&1)
            res=res*a%p;
        b>>=1;
        a=a*a%p;
    }
    return res;
}
inline int c(int x,int y)
{
    return fac[x]*inv[y]%p*inv[x-y]%p;
}
int lucas(int x,int y)
{
    if(!x||!y)
        return 1;
    return c(x%p,y%p)*lucas(x/p,y/p)%p;
}
signed main()
{
    scanf("%lld",&t);
    while(t--)
    {
        scanf("%lld%lld%lld",&n,&m,&p);
        int tmp=n;
        n=n+m;
        m=tmp;
        fac[0]=inv[0]=1;
        for(register int i=1;i<=n;++i)
        {
            fac[i]=fac[i-1]*i%p;
            inv[i]=pw(fac[i],p-2);
        }
        printf("%lld\n",lucas(n,m));
    }
    return 0;
}

5. 莫比乌斯函数

定义：

\begin{aligned} 1\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (n=1) \\ (-1)^k\ \ \ \ (n=\prod_{i=1}^kp_i(p_i\in prime))\\ 0\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (\mathrm{otherwise}) \\ \end{aligned} \right.

莫比乌斯反演：若 f(n)=\sum_{d\mid n}g(d)，则 g(n)=\sum_{d\mid n}\mu(d)f(\frac n d)。

这个反演也可以理解成卷积：若 g*1=f，那么 f*\mu=g。

性质：\sum_{d\mid n}\mu(d)=[n=1]

证明：n=1 显然成立。

设 n=\prod_{i=1}^mp_i^{a_i}(p_i\in prime)，那么所有 \mu(d) 非零的位置必然是在 p_1,p_2,\dots,p_m 中选择若干个乘起来得到的，共有 2^m 个位置。

只考虑 p_1，依据是否选择 p_1 可以将 2^m 个数分成两组，不妨设含 p_1 的一组为 A，不含的一组为 B，显然每组有 2^{m-1} 个数。

有一个显然的结论：\forall d\in B,p_1d\in A。这是因为 A,B 中的元素是一一对应的。那么在 B 中 \mu(d)=-1 的 d，\mu(p_1d)=1，因为多了一个素因子 p_1，反过来也同理，由此我们得到了 \sum_{d\in A}[\mu(d)=1]=\sum_{d\in B}[\mu(d)=-1] 和 \sum_{d\in A}[\mu(d)=-1]=\sum_{d\in B}[\mu(d)=1]，所以在 2^m 个数中 \mu(d)=1 和 \mu(d)=-1 的个数是相等的，因此相加为零。

得证。

例题：求 \phi(i)=\sum_{i=1}^n\varphi(i)。

这玩意可以直接杜教筛 \phi(i)，也可以筛 \mu 的前缀和+数论分块。

杜教筛下面会写，先拿它当一个莫反练手题。

上文提到 \sum_{d\mid n}\varphi(d)=n，刚好是莫反的形式（f(n)=\mathrm{id},g(n)=\varphi(n)），直接莫反一下代入上式。

\phi(i)=\sum_{i=1}^n\sum_{d\mid i}\mu(d)\frac i d

接下来套路地先枚举 d。

\phi(i)=\sum_{d=1}^n\mu(d)\sum_{i=1}^{\lfloor\frac n d\rfloor}i

前半部分杜教筛，后半部分数论分块。

6.杜教筛

杜教筛可以在低于线性的时间内求积性函数的前缀和。他的思想是暴力筛出较小的一些函数值，在较大的定义域上递归求解。

假设我们要求 S(n)=\sum_{i=1}^nf(i)，现在我们假设通过一种玄妙的手段找来另一个函数 g(i)，现在把他俩卷起来得到 h(i) ，对 h 求一个前缀和：

\sum_{i=1}^nh(i)=\sum_{i=1}^n\sum_{d|i}g(d)f(\frac i d) =\sum_{d=1}^ng(d)\sum_{i=1}^{\lfloor\frac n d\rfloor}f(i)=\sum_{d=1}^ng(d)S(\lfloor\frac n d\rfloor)

我们想要 S(n)，我们发现 h(i) 的前缀和大致相当于 g*S（虽然不完全是），所以在前缀和里面会有一项 g(1)S(n)，g(1) 显然是易得的，于是我们决定看看这个怎么算。

利用前缀和思想可以得到:

g(1)S(n)=\sum_{i=1}^ng(i)S(\lfloor\frac n i\rfloor)-\sum_{i=2}^ng(i)S(\lfloor\frac n i\rfloor) =\sum_{i=1}^nh(i)-\sum_{i=2}^ng(i)S(\lfloor\frac n i\rfloor)

我会递归！只要快速计算 h(i) 和 g(i) 的前缀和就好了！问题圆满解决……了吗？

我们似乎还不知道 g(i) 是什么。事实上这在不同的题目里是不同的，但选取 g(i) 的原则是一致的：需要使得 h(i) 和 g(i) 的前缀和均易于计算。

下面有几个例子帮助理解 g(i) 的选取。

朴素杜教筛复杂度 O(n^{\frac 3 4})，做一些优化可以达到 O(n^{\frac 2 3})。

例题：【模板】杜教筛（Sum），就是上面两个例子合起来。

#include<iostream>
#include<cstdio>
#include<map>
using namespace std;
#define int long long
int t,n,phi[5000001],mu[5000001],p[5000001],cnt;
bool vis[5000001];
map<int,int> sphi,smu;
inline void init()
{
    mu[1]=phi[1]=1;
    for(register int i=2;i<=5000000;++i)
    {
        if(!vis[i])
        {
            p[++cnt]=i;
            phi[i]=i-1;
            mu[i]=-1;
        }
        for(register int j=1;j<=cnt&&p[j]*i<=5000000;++j)
        {
            vis[p[j]*i]=1;
            if(i%p[j]==0)
            {
                phi[p[j]*i]=p[j]*phi[i];
                break;
            }
            else
            {
                phi[p[j]*i]=(p[j]-1)*phi[i];
                mu[p[j]*i]=-mu[i];
            }
        }
    }
    for(register int i=2;i<=5000000;++i)
    {
        phi[i]+=phi[i-1];
        mu[i]+=mu[i-1];
    }
}
int getphi(int n)
{
    if(n<=5000000)
        return phi[n];
    if(sphi[n])
        return sphi[n];
    int res=n*(n+1)/2;
    for(register int i=2,j;i<=n;i=j+1)
    {
        j=n/(n/i);
        res-=(j-i+1)*getphi(n/i);
    }
    return sphi[n]=res;
}
int getmu(int n)
{
    if(n<=5000000)
        return mu[n];
    if(smu[n])
        return smu[n];
    int res=1;
    for(register int i=2,j;i<=n;i=j+1)
    {
        j=n/(n/i);
        res-=(j-i+1)*getmu(n/i);
    }
    return smu[n]=res;
}
signed main()
{
    scanf("%lld",&t);
    init();
    while(t--)
    {
        scanf("%lld",&n);
        printf("%lld %lld\n",getphi(n),getmu(n));
    }
    return 0;
}

7.二次剩余

定义及求解

定义：m>1，若 \gcd(n,m)=1 且 x^2\equiv n(mod\ m) 有解，那么称 n 是 m 的二次剩余。

勒让德符号：若n\equiv 0(mod\ m)，那么 (\frac n m)=0，否则，若 n 是 m 的二次剩余，那么 (\frac n m)=1，否则 (\frac n m)=-1。

定理：p\in prime，则 p 的缩系中恰好有一半数是二次剩余，另一半不是。

证明：素数，则小于 p 的正整数都在缩系里。首先证明存在 \frac{p-1}2 个二次剩余。假设他们分别为 1^2\%p,2^2\%p,\dots,(\frac{p-1}2)^2\%p。他们显然都是二次剩余，我们只要证明他们两两互不相同即可。

假设 \exists1\leq i<j\leq\frac{p-1}2,i^2\equiv j^2(mod\ p)，那么有 (j+i)(j-i)\equiv 0(mod\ p)。显然 j-i<j+i<p，矛盾。

因此存在 \frac{p-1}2 个二次剩余。

加下来证明只有 \frac{p-1}2 个二次剩余。我们考虑刚才没有选中的 (\frac{p+1}2)^2\%p,(\frac{p+3}2)^2\%p,\dots,(p-1)^2\%p，容易发现 1^2\equiv(p-1)^2(mod\ p),2^2\equiv(p-2)^2(mod\ p)，以此类推，两组二次剩余一一对应，因此二次剩余恰有 \frac{p-1}2=\frac{\varphi(p)}2 个。

得证。

欧拉判别法：若 p\in\complement_{prime}{\{2\}}，则 n^{\frac{p-1}2}\equiv(\frac n p)(mod\ p)。

证明：如果 n 是二次剩余，那么令 n=x^2\%p，那么左边变成 x^{p-1}\%p，由费马小定理得到左边=右边=1，成立。

如果 n 不是二次剩余，根据拉格朗日定理（n 次同余方程最多有 n 个解），n^{\frac{p-1}2}\equiv1(mod\ p) 这一同余方程至多有 \frac{p-1}2 个解，而二次剩余恰好有 \frac{p-1}2 个，所以每一个解对应一个二次剩余，不是二次剩余左边一定不是 1。但根据费马小定理，我们知道 (n^{\frac{p-1}2})^2=n^{p-1}\equiv1(mod\ p)，那么 n^{\frac{p-1}2} 就只能是 -1 了。

得证。

由欧拉判别法还可以得到勒让德符号是一个积性函数，因为 (\frac n p)(\frac m p)\equiv n^{\frac{p-1}2}m^{\frac{p-1}2}\equiv (nm)^{\frac{p-1}2}\equiv(\frac{nm}p)(mod\ p)。

还可以简单地得到两个二次剩余或两个非二次剩余乘积是二次剩余，一个二次剩余和一个非二次剩余的乘积是非二次剩余。

以下是手算二次剩余的方法，偏 MO，不感兴趣的可以略过。

根据勒让德符号的积性，算 (\frac n p) 时可以直接把 n 质因数分解，然后直接求素数是否为二次剩余即可。

定理：(\frac 2 p)=(-1)^{\frac{p^2-1} 8}。

Gauss 二次互反律：p,q\in\complement_{prime}{\{2\}},p\not=q，则 (\frac p q)(\frac q p)=(-1)^{\frac{(p-1)(q-1)}4}。

通过上述两个定理可以快速手算 (\frac n m)

下面是 OI 中计算二次剩余的方法。

定理：对于二次剩余方程 x^2\equiv n(mod\ p)，p 是奇素数，找到一个 a 使得 (\frac{a^2-n} p)=-1，那么 x=(a+\sqrt{a^2-n})^{\frac{p+1}2} 是原方程的解。其中对非二次剩余的部分开根类似于复数，有一套新的运算法则，可以做模板题了解一下。

证明：可以去看模板题题解，我因为懒就不写了。

例题：【模板】二次剩余

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<ctime>
using namespace std;
#define int long long
int inv,t,n,mod;
struct cp
{
    int x,y;
    cp(int x_,int y_):
        x(x_),y(y_){}
    cp operator *(const cp &other) const
    {
        return cp((x*other.x%mod+inv*y%mod*other.y%mod)%mod,(x*other.y%mod+y*other.x%mod)%mod);
    }
};
inline cp pw(cp a,int b)
{
    cp res=cp(1,0);
    while(b)
    {
        if(b&1)
            res=res*a;
        b>>=1;
        a=a*a;
    }
    return res;
}
signed main()
{
    srand(time(NULL));
    scanf("%lld",&t);
    while(t--)
    {
        inv=0;
        scanf("%lld%lld",&n,&mod);
        if(!n)
        {
            puts("0");
            continue;
        }
        if(pw(cp(n,0),(mod-1)>>1).x==mod-1)
        {
            puts("Hola!");
            continue;
        }
        int a=rand()%mod;
        while(!a||pw(cp((a*a%mod-n+mod)%mod,0),(mod-1)>>1).x==1)
            a=rand()%mod;
        inv=(a*a%mod-n+mod)%mod;
        int ans=pw(cp(a,1),(mod+1)>>1).x;
        if(mod-ans<ans)
            ans=mod-ans;
        printf("%lld %lld\n",ans,mod-ans);
    }
    return 0;
}

二次同余式

定理：若 L>0,p>2,p\in prime,p\nmid n，那么 x^2\equiv n(mod\ p^L) 有 1+(\frac n p) 个解。

推广：如果 p=2，L=1 时有一个解；L=2 时若 n\equiv 0(mod\ p^L) 或 n\equiv 1(mod\ p^L) 时有两个解，否则无解；L>2 时若 n\equiv 1(mod\ 8) 有四个解，否则无解。

证明：依然是不会。

例题：求 x^2\equiv1(mod\ n) 的解的个数。

设 n=\prod_{i=1}^mp_i^{a_i}，然后拆了用 CRT 合并。

那么会得到 m 个方程 x^2\equiv 1(mod\ p_i^{a_i})，如果 p_i 有 2 先特判掉，然后根据上面这个定理，每个方程的解的个数和 x^2\equiv 1(mod\ p_i) 是一样的（因为 L 并不影响）。于是搞出来直接乘法原理即可。

高次同余式

定理：x^k\equiv 1(mod\ p)(p\in prime) 有 \gcd(k,p-1) 个解。

将这个定理推广，可得 x^k\equiv n(mod\ p)(p\in prime) 在 p\nmid n 时无解或有 \gcd(k,p-1) 个解。

8.升幂问题

升幂定理：若 p 是奇素数，p\nmid ab,p\mid a-b，那么 a^n-b^n 中 p 的幂次等于 a-b 中 p 的幂次与 n 中 p 的幂次之和。