简单数学

一月 01, 2022

数论

常见概念和符号

整除/同余常见符号

整除符号 $x\mid y$，表示 $x$ 整除 $y$ ，即 $x$ 是 $y$ 的因数
取模符号 $x \bmod y$ ，表示 $x$ 除以 $y$ 以后的余数
互质符号 $x~\bot~y$ ，表示 $x$ ，$y$ 互质
最大公约数 $\gcd(x,y)$
最小公倍数 $\text{lcm} (x,y)$

数论函数常见符号

求和符号：$\sum$ 符号，表示满足特定条件的数的和

$\sum _{i=1} ^{n} ai$ 表示 $a_1\sim a_n$ 的和
$\sum_{S\subseteq T} |S|$

求积符号：$\Pi$ 符号，表示满足特定条件的数的积

$\Pi_{i=1}^n$ 表示 $n!$
$\Pi _{i=1}^{n} a_i$ 表示从 $a_1\sim a_n$ 的积
$\Pi _{x\mid d} x$ 表示 $d$ 的所有因数的乘积

整除符号：$\mid$ ，$a \mid b$ 表示 $a$ 是 $b$ 的约数 $b$ 不被 $a$ 整除记作 $a \nmid b$ 。

同余符号：$\equiv$ ，$a\equiv b \pmod c$ 表示 $\dfrac a c -\lfloor \dfrac a c \rfloor=\dfrac b c-\lfloor \dfrac b c \rfloor$ 或者说 $a/c$ 和 $b/c$ 的余数相同

数论函数

数论函数指定义域为正整数的函数。数论函数也可以视作一个数列。

积性函数

若 $f(n)$ 表示 $f(1)=1$ 且 $\forall x,y \in N_+$ $\gcd(x,y)=1$ 都有 $f(xy)=f(x)f(y)$，则 $f(n)$ 为积性函数

若 $f(n)$ 表示 $f(1)=1$ 且 $\forall x,y \in N_+$ 都有 $f(xy)=f(x)f(y)$，则 $f(n)$ 为完全积性函数

导数公式

$(C)^{‘}=0$ $(x^\mu)’=\mu x^{\mu-1}$

$(a^x)’=a^x\ln x$ ( $a$ 为常数） $(\sin x)’=\cos x$

$(\cos x)’=-\sin x$ $(\tan x)’=\sec^2x$

$(\cot x)’=-\csc^2x$ $(\sec x)’=\sec x \cot x$

$(\csc x)’=-\csc x\cot x$ $(\ln x)’=\dfrac{1}{x}$

$({\log_a}^x)’=\dfrac{1}{x\ln a}$ $(e^x)’=e^x$

加减公式：

$(u\pm v)’=u’\pm v’$ $(Cu)’=Cu’$ （C是常数）

$(uv)’=u’v+uv’$ $(\dfrac{u}{v})’=(\dfrac{u’v-uv’}{v^2})$

复数

设$a,b$为实数，$i^2=-1$，形如$a+bi$的数叫复数，其中$i$被称为虚数单位，复数域是目前已知最大的域

在复平面中，$x$ 代表实数，$y$ 轴（除原点外的点）代表虚数，从原点$(0,0)$到$(a,b)$的向量表示复数$a+bi$

模长：从原点$(0,0)$到点$(a,b)$的距离，即$\sqrt{a^2+b^2}$

幅角：假设以逆时针为正方向，从xx轴正半轴到已知向量的转角的有向角叫做幅角

计算：平行四边形法则(其实就是分配律)，注意这里的$i^2$为-1：

几何定义：复数相乘，模长相乘，幅角相加~~(至今我也没看懂)~~

$(a+bi)\times (c+di)=ac+bdi^2+bci+adi=ac-bd+(bc+ad)i$

同时，我们由向量的知识迁移到复数上来，定义 复数的模 就是复数所对应的向量的模。

复数 $z=a+bi$ 的模 $|z|=\sqrt{a^2+b^2}$

于是为了方便，我们常把复数 $z=a+bi$ 称为点 $Z$

由向量的知识我们发现，虚数不可以比较大小

复数满足交换律，结合律，对加法的分配律

当两个虚数实部相等，虚部互为相反数时，这两个复数互为 共轭复数。

即 $z=a+bi$ 的共轭复数为 $z=a-bi$

位运算

一般均是在二进制下来说

基本运算

1.与 (&) 两个对应位都为 $1$ 时才为 $1$

2.或 (|) 只要两个对应位中有一个 $1$ 时就为 $1$

3.异或(^) 只有两个对应位不同时才为 $1$

取反(~)

把0变成1，把1变成0

补码：在二进制表示下，正数和的补码为其本身，负数的补码是将其对应正数按位取反后加一。

应用：$\text{lowbit}(x)=(x)\&(-x)$ 取出最后一个等于1的位数，具体原因想一想

左移和右移

num<<i 表示将 $num$ 的二进制表示向左移动1位所得的值。

num>>i 表示将 $num$ 的二进制表示向右移动1位所得的值。

注意：+ 和-的优先级高于左移右移

高精度

#include<iostream>
#include<string.h>
#include<stdio.h>
#include<cstdlib>
#include<algorithm>
#define base 100000
#define cut 5
#define L 10000
using namespace std;

struct Big{
    int len;
    long long num[L];
    Big(){
        len=1;
        memset(num,0,sizeof(num));
    }
    Big operator=(const Big &a){
        len=a.len;
        for(int i=0;i<len;i++) num[i]=a.num[i];
        return *this;
    }
    long long &operator[](int a){
        return num[a];
    }
    long long operator[](int a)const{
        return num[a];
    }
    friend istream&operator>>(istream&,Big&);
    friend ostream&operator<<(ostream&,Big&);
};

int operator>(const Big a,const Big b){
    if(a.len!=b.len){
        if(a.len>b.len) return 1;
        return 0;
    }
    for(int i=a.len-1;i>=0;i--)
	    if(a[i]>b[i]) return 1;
    return 0;
}

int operator==(const Big a,const Big b){
    if(a.len!=b.len) return 0;
    for(int i=0;i<a.len;i++)
     if(a[i]!=b[i])
      return 0;
    return 1;
}

int operator<(const Big a,const Big b){
    if(a>b || a==b)return 0;
    return 1;
}

Big operator+(Big a,Big b){
    Big ret;
    long long carry=0;
    for(int i=0;;i++){
        ret[i]=a[i]+b[i]+carry;
        carry=ret[i]/base;
        ret[i]%=base;
        if(i>=a.len&&i>=b.len&&carry==0)
         break;
    }
    ret.len=min(L,max(a.len,b.len)+10);
    while(ret.len>0&&ret[ret.len-1]==0)
     ret.len--;
    if(ret.len==0)
     ret.len=1;
    return ret;
}

Big operator+(Big a,int b){
    long long carry=b;
    for(int i=0;;i++){
        a[i]+=carry;
        carry=a[i]/base;
        a[i]%=base;
        if(a[i]==0 && carry==0 && i>=a.len)
         break;
    }
    a.len=min(L,a.len+10);
    while(a.len>0 && a[a.len-1]==0) a.len--;
    return a;
}

Big operator*(Big a,Big b){
    Big ret;
    for(int i=0;i<a.len;i++)
        for(int j=0;j<b.len;j++) ret[i+j]+=a[i]*b[j];
    long long carry=0;
    for(int i=0;;i++){
        ret[i]+=carry;
        carry=ret[i]/base;
        ret[i]%=base;
        if(ret[i]==0 && carry==0 && i>=a.len+b.len-1) break;
    }
    a.len=min(L,a.len+b.len+10);
    while(a.len>0 && a[a.len-1]==0) a.len--;
    return a;
}

Big operator*(Big a,int b){
    long long carry=0;
    for(int i=0;;i++){
        carry+=a[i]*b;
        a[i]=carry%base;
        carry/=base;
        if(carry==0&&a[i]==0&&i>=a.len) break;
    }
    a.len=min(L,a.len+10);
    while(a.len>0&&a[a.len-1]==0) a.len--;
    return a;
}

Big operator-(Big a,Big b){
    long long carry=0;
    for(int i=0;;i++){
        a[i]-=b[i]+carry;
        if(a[i]<0) carry=(-a[i]/base+1);
        else carry=0;
        a[i]+=carry*base;
        if(carry==0&&i>=b.len) break;
    }
    while(a.len>0&&a[a.len-1]==0) a.len--;
    return a;
}

Big operator-(Big a,int b){
    long long carry=b;
    for(int i=0;;i++){
        a[i]-=carry;
        if(a[i]<0) carry=(-a[i]/base+1);
        else carry=0;
        a[i]+=carry*base;
        if(carry==0) break;
    }
    while(a.len>0 && a[a.len-1]==0) a.len--;
    return a;
}

Big operator/(Big a,int b){
     long long carry=0;
     for(int i=a.len-1;i>=0;i--){
         a[i]+=carry*base;
         carry=a[i]%b;
         a[i]/=b;
     }
     while(a.len>0&&a[a.len-1]==0) a.len--;
     return a;
}

Big operator%(const Big a,int b){
     return a-(a/b)*b;
}

int main(){
    return 0;
}

数论

整除性质

$\begin{aligned} &a\mid b \Longleftrightarrow-a\mid b \Longleftrightarrow a\mid -b \Longleftrightarrow|a| \mid \lvert b\rvert \\ &a\mid b \wedge b\mid c \Rightarrow a \mid c \\ &a\mid b \wedge a\mid c \Longleftrightarrow \forall x, y \in \mathbb{Z}, a \mid x b+y c \\ &a\mid b \wedge b\mid a \Rightarrow b=\pm a \\ &\text{设 } m \neq 0 \text { ，那么 } a\mid b \Longleftrightarrow m a\mid m b \text { } \\ &\text{设 } b \neq 0 \text { ，那么 } a\mid b \Rightarrow\mid a\mid \leq\mid b \mid \\ &\text{设 } a \neq 0, b=q a+c \text { ，那么 } a\mid b \Longleftrightarrow a\mid c_{。} \end{aligned}$

同余性质

$\begin{aligned} &\text { - 自反性: } a \equiv a(\bmod m) . \\ &\text { - 对称性: 若 } a \equiv b(\bmod m) \text {, 则 }~ b \equiv a(\bmod m) ~. \\ &\text { - 传递性: 若 } a \equiv b(\bmod m), b \equiv c(\bmod m) \text {, 则 } a \equiv b(\bmod m) . \\ &\text { - 线性运算: 若 } a, b, c, d \in \mathbf{Z}, m \in \mathbf{N}^{*}, a \equiv b(\bmod m), c \equiv d(\bmod m) \text { 则有: } \\ &\text { - } a \pm c \equiv b \pm d(\bmod m) \text {. } \\ &\text { - } a \times c \equiv b \times d(\bmod m) \text {. } \\ &\text { - 若 } a, b \in \mathbf{Z}, k, m \in \mathbf{N}^{*}, a \equiv b(\bmod m) \text {, 则 } a k \equiv b k(\bmod m k) . \\ &\text { - 若 } a, b \in \mathbf{Z}, d, m \in \mathbf{N}^{*}, d\mid a, d\mid b, d \mid m, \text { 则当 } a \equiv b(\bmod m) \text { 成立时，有 } \\ &\frac{a}{d} \equiv \frac{b}{d}\left(\bmod \frac{m}{d}\right) . \\ &\text { - 若 } a, b \in \mathbf{Z}, d, m \in \mathbf{N}^{*}, d \mid m, \text { 则当 } a \equiv b(\bmod m) \text { 成立时，有 } a \equiv b(\bmod d) . \\ &\text { - 若 } a, b \in \mathbf{Z}, d, m \in \mathbf{N}^{*} \text {, 则当 } a \equiv b(\bmod m) \text { 成立时，有 } \operatorname{gcd}(a, m)=\operatorname{gcd}(b, m), \\ &\text { 若 } d \text { 能整除 } m \text { 及 } a, b \text { 中的一个，则 } d \text { 必定能整除 } a, b \text { 中的另一个。 } \end{aligned}$

最大公约数与最小公倍数

若干个数所有约数中的共同的最大数是最大公约数，倍数中共同的最小数是最小公倍数

一般两个数的最大公约数是 $\gcd$ 最小公倍数是 $\mathrm{lcm}$

$\gcd(a,b)\mathrm{lcm}(a,b)=ab$

求法：辗转相除

1	int gcd(int a,int b){return a%b==0?a:gcd(b,a%b);}

整除分块

整除分块是用于快速处理形似

$\sum _ {i=1} ^n \lfloor \dfrac n i\rfloor$

的式子的办法

引理1

$\forall a,b,c \in Z,\lfloor \dfrac a {bc} \rfloor =\lfloor \dfrac{\lfloor \frac a b \rfloor} c \rfloor$

证明略

引理2

对于一个较大的 $n$ 我们显然会发现，我们后面的这个下取整取值并不是每一次都随着 $i$ 而变化的，它是呈块状分布的，同时这个下取整的值我们也能得到，应该是共有 $2\sqrt n$ 个值

结论：

通过严谨的数学推理~~(打表)~~ 我们发现实际上这些取值是有规律的，即

如果一个块的开始位置时 $l$ 那么它的结束位置 $r$ 就是 $\lfloor \dfrac n {\lfloor \frac n l \rfloor} \rfloor$

那么我们写程序的基本结构就很显然了

1	for(int l=1,r;l<=n;l=r+1) r=n/(n/l);

所以我们对于形如：

$\sum _{i=1} ^ n f(i)\lfloor \dfrac n i\rfloor$

可以对 $f(i)$ 可以直接前缀和预处理，就可以解决这道问题了

欧拉函数

$φ(n)$ :定义：1~n中与n互质的数的个数

公式：

$设N=p1^{α1}*p2^{α2}*p3^{α3}...$ $则\varphi(N)= N*(1-\frac{1}{p1})*(1-\frac{1}{p2})...$

莫比乌斯函数

我们一般表示为 $\mu(x)$

$\exists d_i\ge 2$，$\mu(x)=0$
$\forall d_i=1$，$\mu(x)=(-1)^k$ ($k$ 是质因数分解后有几项)
$x=1$ ，$\mu(x)=1$

如：

$\mu(6)=1$ $\mu(7)=-1$ $\mu(8)=0$

设 $s(n)=\sum_{i=d\mid n}^{n} \mu (i)$

如 $s(6) = \mu(1) +\mu(2) +\mu(3) +\mu(6)$

那么：

当 $n=1$，$s(n)=1$
当 $n>1$，$s(n)=0$

对于2的证明：

首先我们对于 $n$ 因式分解：$n=p_1^{\alpha_1}\times p_2^{\alpha_2}\times\dots\times p_k^{\alpha_k}$ ($k\ge 1$)

那么我们的每一个 $d$ 都有：$d=p_1^{\beta_1}\times p_2^{\beta_2}\times\dots\times p_k^{\beta_k}$ ($\forall i \in [1,k]$ $0\le\beta_i\le \alpha_i$)

那么我们算一下 $\mu(d)$ 可知，我们只需要考虑，如果$\exists i \in [1,k]$，$\beta_i\ge 2$ 则原式为0

所以我们只需要看里面有多少个1即可

所以我们用组合数算一下：

$\mu(x)=\sum_{i=0}^{k} \binom k i (-1)^i$

我们这时候看一下二项式定理：

$(a+b)^k=\sum _{i=0}^{k} \binom k i a^i b^{k-i}$

钦定 $a=1$ $b=-1$

$(1-1)^k=\sum_{i=0}^{k} \binom k i (-1)^i=0$

所以 $\mu(x)$ 必然等于=0，得证

各种筛法

埃氏筛

用于统计从1-n中的质数

原理：从前往后筛，如果筛到一个数$i$，然后把$i$的倍数都删了

时间复杂度：$O(nlog^2n)$ 基本可以跑到3e5

void statistics(int n){
    for(int i=2;i<=n;i++){
        if(!st[i]) prime[++k]=i;
        for(int j=1;prime[j]*i<=n;j++){
            st[prime[j]*i]=true;
        }
    }
}

线性筛

这个东西很重要，关系到后面的积性函数求解

先放一个代码：

void primes(int n){
    for(int i=2;i<=n;i++){
        if(!st[i]) prime[++k]=i;
        for(int j=1;prime[j]*i<=n;j++){
            st[i*prime[j]]=true;
            if(!(i%prime[j])) break;
        }
    }
}

我们观察和上面那个的区别

发现无非就是多了一行if(i%prime[j]==0) break;

我们先给个证明来说明这句话加上后的正确性

证明

当$i$是$prime[j]$的整数倍时$\iff prime[j]\mid i$

设 $k=i/prime[j]$

则 $iprime[j+1]=prime[j](prime[j+1]*k)$

所以说 $i*prime[j]$ 是 $prime[j]$ 的整数倍

不需要继续标记

对于 $prime[j+2]*i$ 等同理，所以说可以直接跳出循环，不需要重新标记

这样线性筛的复杂度就可以被优化到 $O(n)$ 了

欧拉筛

我们可以把这件求phi分成两步

k是质数

首先我们容易发现一个问题：如果$k$是质数，那么$\varphi (k)$显然等于$k-1$，因为小于$k$的数都与$k$互质

所以我们可以把这一句：if(!vis[i]) p[++num]=i;再加上一句phi[i]=i-1;

$i\%p=0$ 时

然后我们需要证明一个东西：

若$p\mid i$且$p$为质数则 $\varphi(ip)$=$p\varphi(i)$

证明：

若$p \mid i$ 则可以推出$p$ 是 $i$ 的一个质因子

我们发现：一个数的欧拉函数与每一项的次数无关

所以说
$\varphi(i*p)=i*p*(1-\frac{1}{p_1})*(1-\frac{1}{p_2})...*(1-\frac{1}{p_k})$
同时
$\varphi(i)=i*(1-\frac{1}{p_1})*(1-\frac{1}{p_2})...*(1-\frac{1}{p_k})$
发现两个式子除了 $i*p$ 全部相同

所以我们可以推出 $\varphi(ip)$=$p\varphi(i)$

证毕

那么很显然在这一句中if(i%prime[j]==0) break;我们可以加上phi[prime[j]*i]=prime[j]*phi[i]
$i\%p!=0$ 时

$p$ 一定是 $i*p_j$ 的最小质因子

先把 $\varphi(i)$ 的式子摆在这
$\varphi(i)=i*(1-\frac{1}{p_1})*(1-\frac{1}{p_2})...*(1-\frac{1}{p_k})$
然后
$\varphi(p*i)=p*i*(1-\frac{1}{p_1})*(1-\frac{1}{p_2})...*(1-\frac{1}{p_k}*(1-\frac{1}{p}))$
我们把下面的式子除以上面的式子发现：
$\varphi(p*i)/\varphi(i)=p*(1-\frac{1}{p})=p-1$
把 $\varphi(i)$ 挪到右边最后可以得到
$\varphi(p*i)=\varphi(i)*(p-1)$
所以我们讨论完了所有的情况，可以得到最终式子：

inline void get_euler(int n){
    phi[1]=1;
    for(int i=2;i<=n;i++){
        if(!st[i]){
            phi[i]=i-1;
            prime[++cnt]=i;
        }
        for(int j=1;prime[j]*i<=n && j<=cnt;j++){
            st[prime[j]*i]=true;
            if(i%prime[j]==0){
                phi[i*prime[j]]=prime[j]*phi[i];
                break;
            }
            phi[i*prime[j]]=phi[i]*(prime[j]-1);
        }
    }
}

莫比乌斯筛

这个比较简单，就不写了

inline void get_euler(int n){
    phi[1]=1;
    for(int i=2;i<=n;i++){
        if(!st[i]){
            mu[i]=-
            phi[i]=i-1;
            prime[++cnt]=i;
        }
        for(int j=1;prime[j]*i<=n && j<=cnt;j++){
            st[prime[j]*i]=true;
            if(i%prime[j]==0){
                phi[i*prime[j]]=prime[j]*phi[i];
                break;
            }
            mu[i*prime[j]]=-mu[i];
            phi[i*prime[j]]=phi[i]*(prime[j]-1);
        }
    }
}

分解质因数

试除法

用于单个数检验是否为质数

原理：从1枚举到$\sqrt n$观察是否有数能被n整除

void prime(int x){
    int n=x;
    for(int i=2;i*i<=n;i++){
        if(x%i==0) 
            while(n%i==0) 
                vec[x].push_back(i),n/=i;
    }
    if(n) vec[x].push_back(n);
}

Miller-Rabin

用法：$O(k\log^2n)$ 判断 $n$ 是否是质数。其中 $k$ 是枚举底数的个数，$2^{78}$ 以内只需要枚举 $12$ 个。

费马小定理：

若 $p$ 是质数且 $p \nmid a$

$a^{p-1} \equiv 1 \pmod p$

我们可以根据费马小定理得出一种检验素数的思路(Fermat 素性测试)：

它的基本思想是不断地选取在 $[2,n)$ 中的 $a$，并检验是否每次都有 $a^{n−1}\equiv 1 \pmod n$

但是很遗憾，费马小定理的逆定理并不成立

卡迈克尔数：如果有一个合数 $n$ 满足任何一个 $a$ 都满足 $a^{n−1}\equiv 1 \pmod n$，那么我们称这个合数 $n$ 为卡迈克尔数，同时，满足 $m=2^n-1$ 那么 $m$ 还是卡迈克尔数，所以卡迈克尔数是无穷的

二次探测定理：

若 $p$ 是奇素数，则 $x^2 \equiv 1 \pmod p$ 的解为 $x=1$ 或 $x=p-1$ $\pmod p$

算法流程：

（1）对于偶数和 0，1，2 可以直接判断。

（2）设要测试的数为 $x$，我们取一个较小的质数 $a$，设 $s,t$，满足$2^s\times t=x-1$ （其中 $t$ 是奇数）。

（3）我们先算出 $a^t$，然后不断地平方并且进行二次探测（进行 $s$ 次）。

（4）最后我们根据费马小定律，如果最后 $a^{x-1}\not\equiv 1 \pmod x$，则说明 $x$ 为合数。

（5）多次取不同的 $a$ 进行 $Miller-Rabin$ 素数测试，这样可以使正确性更高

备注：

（1）我们可以多选择几个 $a$，如果全部通过，那么 $x$ 大概率是质数。

（2）$Miller-Rabin$ 素数测试中，“大概率”意味着概率非常大，基本上可以放心使用。

（3）当 $a$ 取前12个素数时，可以证明 $2^{78}$ 范围内的数不会出错。

（5）另外，如果是求一个 $\text{long long}$ 类型的平方，可能会爆掉，因此有时我们要用快速乘，不能直接乘。

$\text{Pollard-Rho}$ 先咕了

裴蜀定理

对于二元一次方程 $ax+by=c$，有整数解的充要条件是 $\gcd(a,b) \mid c$。

推论：当 $ax+by=1$ 时，当且仅当 $\gcd(a,b)=1$ 时有解。

证明：

设 $d=\gcd(a,b)$ 则 $d \mid a,d\mid b$。由整除的性质 $\forall x,y\in Z$，有 $d \mid (ax+by)。$

设 $s$ 为 $ax+by$ 最小正值，令 $q=\left\lfloor \dfrac{a}{s} \right\rfloor$。

则 $r=a\pmod s=a-q(ax+by)=a(1-qx)+b(-qy)$。

可见 $r$ 也为的线性组合。

由于 $r$ 为 $a\pmod s$ 所得，所以 $0\leq r<s$。

由于 $s$ 为线性组合的最小正值,可知。

因此有 $ s\mid a$ ，同理 $s\mid b$ ，因此，$s$ 是 $a$ 与 $b$ 的公约数，所以 $d\ge s$。

因为 $d\mid a$ ，$d\mid b$ ，且 $s$ 是 $a$ 与 $b$ 的一个线性组合，所以由整除性质知 $d\mid s$。
但由于 $d\mid s$ 和 $s>0$，因此 $d\le s$。

由 1,2 得 $d=s$ ，命题得证。

exgcd

现在我们对于 $ax+by=c$ 想要获得一组整数解。

首先 $c$ 肯定是要满足 $\gcd(a,b) \mid c$ 的（~~要不然裴蜀定理白证明了~~）。

然后我们可以直接求 $a_1x+b_1y=\gcd(a_1,b_1)$ 的一组整数解，最后 $x,y$ 再乘上 $c/\gcd(a_1,b_1)$ 即可

好了，我们现在说怎么求解。

当 $b=0$ 时，显然 $x=1,y=0$

当 $b\not= 0$ 时，有：

$ax+by=\gcd(a,b)$

$\because\gcd(b,a\bmod b)=\gcd(a,b)$

$\therefore a x + b y = \gcd ( a , b ) = \gcd ( b , a \bmod b ) = b \times t x + ( a \bmod b ) \times t y$

$\because a \bmod b=a- \left\lfloor \dfrac{a}{b} \right\rfloor\times b$

$\therefore a x+b y=b\times tx+(a- \left\lfloor \dfrac{a}{b} \right\rfloor\times b)\times ty=a\times ty+b\times(tx−\left\lfloor \dfrac{a}{b} \right\rfloor\times ty)$

$\therefore x=ty,y=tx-\left\lfloor \dfrac{a}{b} \right\rfloor\times ty$

此时我们容易发现： $x$ 和 $y$ 都被转化成了两个更小的数，然后递归求解即可

#include<cstdio>#include<algorithm>#include<cmath>#include<cstdlib>#define ll long long using namespace std;ll exgcd(ll a,ll b,ll &x,ll &y){	if(!b){		x=1;y=0;		return a;	}	else{		ll tx,ty;		ll d=exgcd(b,a%b,tx,ty);		x=ty;y=tx-(a/b)*ty;		return d;	}}int main(){	ll a,b,k,x,y;scanf("%lld%lld%lld",&a,&b,&k);	ll d=exgcd(a,b,x,y);	if(k%d){puts("no solution!");return 0;}	else{		x=x*k/d;		y=(k-a*x)/b;	}	printf("%lld %lld\n",x,y);	return 0;}

欧拉定理

$\text{若 }\gcd(a,m)=1, \text{则 }a^{\varphi(m)\equiv 1}\pmod m$

证明：

设 $x_1,x_2,\dots,x_{\varphi(m)}$ 是 $[1,m]$ 里面与 $m$ 互质的数，由于在 $\bmod m$ 意义下两两不同且余数都与 $m$ 互质

因此我们推理：$ax_i$ 必定也是 $\bmod m$ 意义下两两不同且余数都与 $m$ 互质的数

所以：

$x_1x_2\dots x_{\varphi(m)} \equiv ax_1ax_2\dots ax_{\varphi(m)}\pmod m$ $1\equiv a^{\varphi(m)} \pmod m$

拓展欧拉定理

$a^{b} \equiv \begin{cases}a^{b ~\bmod~ \varphi(m)} & \operatorname{gcd}(a, m)=1 \\ a^b & \operatorname{gcd}(a, m) \neq 1, b<\varphi(m) \quad(\bmod m) \\ a^{(b~ \bmod ~\varphi(m))+\varphi(m)} & \operatorname{gcd}(a, m) \neq 1, b \geq \varphi(m).\end{cases}$

推理：Oi Wiki)

乘法逆元

定义：若 $ax\equiv 1\pmod b$ 且 $a$ 与 $b$ 互质，那么我们就能定义 $x$ 为 $a$ 的逆元，记为 $a^{-1}$ ，所以我们也能称 $x$ 为 $a$ 在 $\pmod b$ 意义下的倒数，此时我们对于 $\dfrac{a}{b}~\pmod p$，我们就可以求出 $b$ 在 $\pmod p$ 意义下的逆元，来代替 $\dfrac{1}{b}$

快速幂

由费马小定理：若 $p$ 为素数，$a$ 为正整数，且 $a$ 、$p$ 互质。则有 $a^{p-1}\equiv 1\pmod p$

所以

$\dfrac{a}{b}=a\times b^{-1}\equiv a\times b^{p-2} \pmod p$

所以我们用快速幂算出来 $a\times b^{p-2}$ 就有 $\dfrac{a}{b}$ 的逆元的值了

#include<iostream>#include<cstdio>#include<queue>#include<algorithm>#include<cstring>#include<cmath>using namespace std;typedef long long ll;int mod;ll power(ll k,ll p){	ll ans=1;	while(p){		if(p&1) ans=ans*k%mod;		k=k*k%mod;		p>>=1;	}	return ans;}ll a,b;int main(){	scanf("%lld%lld",&a,&mod);//算a的逆元	printf("%lld",a*power(b,mod-2)%mod);	return 0;}

拓展欧几里得

求解 $ax\equiv c \pmod b$ 中 $c=1$ 的情况。我们可以转化为求解 $ax+by=1$ 的解

所以：

ll exgcd(ll a,ll b,ll &x,ll &y){	if(!b){		x=1;y=0;		return a;	}	else{		ll tx,ty;		ll d=exgcd(b,a%b,tx,ty);		x=ty;y=tx-(a/b)*ty;		return d;	}}int a,p,x,y;int main(){    scanf("%d%d",&a,&p);    int d=exgcd(a,p,x,y);    x=(x%p+p)%p;}

线性求逆元

首先，我们设 $p=kx+r$

那么我们很容易发现：$kx+r\equiv 0\pmod p$

此时，我们左右同时乘上 $k^{-1}r^{-1}$ 可得

$kr^{-1}+x^{-1}\equiv 0\pmod p$

$\therefore x^{-1}\equiv -kr^{-1}\pmod p$

把 $k=\left\lfloor \dfrac{p}{x} \right\rfloor$ $r=p \bmod x$ 代入，得

$x^{-1}\equiv -\left\lfloor \dfrac{p}{x} \right\rfloor \times (p \bmod i)^{-1} \pmod p$

阶乘求逆元

首先，有如下的一个关系：

$inv_{i+1}=\dfrac{1}{(i+1)!}$

$inv_{i+1}*(i+1)=\dfrac{1}{i!}\times \dfrac{1}{n+1}\times (n+1)=\dfrac{1}{i!}=inv_i^{-1}$

所以我们可以先求出 $n$ 的逆元，然后逆推即可

同时，我们也可以发现 $\dfrac{1}{i}$ 的逆元就是：$\dfrac{1}{i!}\times (i-1)!=\dfrac{1}{n}\pmod p$

Lucas

定理：

$\binom{a}{b}=\binom{a \bmod p}{b \bmod p} \times \binom{\frac{a}{p}}{\frac{b}{p}}\pmod p$

中国剩余定理(CRT)

定理：对于下列一些式子的整数求出符合条件的最小的正整数 $x$

$\left\{ \begin{array}a x\equiv x_1\pmod {m_1}\\ x\equiv x_2\pmod {m_2}\\ ……\\ x\equiv x_n\pmod {m_n} \end{array} \right.$

首先，若$(m_1,m_2\dots m_n)$两两互质

我们即可直接令 $M=m_1\times m_2\dots\times m_n$

则令 $M_i=\dfrac{M}{m_i}$

当 $x$ 满足 $x = x_1\times M_1\times M_1^{-1}+x_2\times M_2\times M_2^{-1}\dots $ 时

一定符合上面的式子

莫比乌斯反演

形式一：

$f(x)=\sum_{d\mid x} g(d) \iff g(x)=\sum_{d\mid x} \mu(d)f(\dfrac x d)$

证明：

$\begin{align*} \sum_{d\mid x} \mu(d)f(\dfrac x d)&=\sum_{d\mid x} \mu(d)\sum_{i\mid \frac x d} g(i)\\ &=\sum_{i\mid x}g(i) \sum_{d\mid \frac x i} \mu(d) \end{align*}$

我们容易发现：对于右边的式子 $\sum_{i\mid x}g(i) \sum_{d\mid \frac x i} \mu(d)$

结合莫比乌斯函数刚才推的性质2，我们很容易得到该式 $=f(x)$

得证

形式二：

$f(n)=\sum_{n\mid d} g(d) \iff \sum_{n\mid d}\mu(\dfrac d n) f(d)$

查看评论