数学能考班里第几啊？ ————唐

模运算

%是个好东西，(~~比如我就每天给RainAir发几个~~)。

突然有一种想把RainAir抱走的感觉(快逃

进入正题：

%运算有这样一个性质：

$$a \% b \leq b$$

如果$b | a$,那么$a \% b = 0$。

~~感觉这不是废话吗？~~

那么再看三个：

$$a \% b = a - \lfloor \frac{a}{b} \rfloor \times b$$

$$( a + b ) \% \;p = ( a \;\% \;p + b \;\% \;p ) \% \;p$$

$$( a \times b ) \% \;p = ( (a \;\% \;p) \times (b \;\% \;p) ) \% \;p$$

仔细思考一下，为什么正确呢？

模运算的原理和性质比较简单，但在OI数学/数论部分有重要的作用。

比如我们马上要讲的乘法逆元和欧几里得算法。

欧几里得算法

欧几里得算法又称辗转相除法，用来求两个数的最大公因数。依据是 $\gcd(a, b) = \gcd(b, a\ \% \ b)$。

代码：

1
2
3

inline long long gcd(long long a,long long b){
    return (!b)?a:gcd(b,a%b);
}

时间复杂度为对数级别。
关于最大公约数还有一个性质是 $\gcd(a, b) \times \operatorname{lcm}(a, b) = a \times b$。

1
2
3

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

乘法逆元

乘法逆元，是指数学领域群$G$中任意一个元素$a$，都在$G$中有唯一的逆元$a_1$，具有性质$a×a_1=a_1×a=e$，其中$e$为该群的单位元。 —-百度百科

~~ctmd这是什么玩意 $\times 1$~~

通俗点的：

若$ax \equiv 1 \% b$, 则称$a$关于$1$模$b$的乘法逆元为x。也可表示为$ax \equiv 1(mod b)$。

~~ctmd这是什么玩意 $\times 2$~~

我们来举个栗子：

$5$关于模$14$的乘法逆元怎么求呢？

因为$5$和$14$互质(证明过程略)

$1=5-4=5-(14-5 \times 2)=5 \times 3-14$

所以，5关于模14的乘法逆元为3。

那么乘法逆元怎么求啊？

先来日常Orz一下平民贵族数学家费马:

费马小定理:
内容：
若$p$为质数，且$gcd(a,b)=1$,那么$a^{p-1} \equiv 1 (mod \; p)$

证明：(以下证明摘自百度百科，侵删)：

引理1：

若$a,b,c$为任意$3$个整数,$m$为正整数，且$(m,c)=1$，则当$ac \equiv bc (mod \;m)$时，有$a \equiv b(mod \;m)$。

证明：$ac \equiv bc(mod \;m)$可得$ac–bc \equiv 0(mod \;m)$可得$(a-b)c \equiv 0(mod \;m)$。因为$(m,c)=1$,即$m,c$互质，$c$可以约去，$a-b \equiv 0(mod \;m)$可得$a \equiv b(mod \;m)$

引理2：

设$m>1(m \in Z)$,$gcd(m,b)(b \in Z)$

如果$a[1],a[2],a[3],a[4],\dots a[m]$是模$m$的一个完全剩余系，

则$b \times a[1],b \times a[2],b \times a[3],b \times a[4],\dots b \times a[m]$也构成模$m$的一个完全剩余系。

若存在$2$个整数$b·a[i]$和$b·a[j]$同余,即

$$b\times a[i] \equiv b \times a[j] \;(mod \;m)$$ ,

$$i,j \geq 1$$

根据引理$1$则有$a[i] \equiv a[j] (mod \;m)$。
根据完全剩余系的定义可知这是不可能的，因此不存在$2$个整数$b \times a[i]$和$b \times a[j]$同余。

所以$b \times a[1],b \times a[2],b \times a[3],b \times a[4],\dots b \times a[m]$构成模$m$的一个完全剩余系。

构造素数$p$的完全剩余系:

$$P=\lbrace 1,2,3,\dots,p-1 \rbrace$$

因为$gcd(a,p)=1$,由引理2可得

$$A =\lbrace a,2a,3a,\dots,(p-1)a \rbrace$$

也是$p$的一个完全剩余系。由完全剩余系的性质，

$$\prod_{i=1}^{p-1} i \equiv \prod_{i=1}^{p-1} i \times a^i \;\;(mod \; p)$$

即：

$$(p-1)! \equiv (p-1)! \times a^{p-1}\;(mod \;p)$$

易得$gcd((p-1)!,p)=1$,同余式两边可约去$(p-1)!$。

得到$a^{p-1} \equiv 1 (mod \; p)$.

这样就证明了费马小定理。

~~ctmd这是什么玩意 $\times 3$~~

好了，来看看如何用费马小定理求乘法逆元：

根据费马小定理：

$a$在$mod \; p$意义下的乘法逆元就是$a^{p-2}$

是不是感觉一下子就清晰了？

代码也特别好写：

1
2
3

inline long long INV_PRIME(long long a,long long p){
	return quick_power(a,p-2,p);
}

注意，这里$p$必须为质数！（最好写快速幂)

扩展欧几里得

求解$ax+by=c(a,b,c,x,y \in Z)$的不定方程
当且仅当$c=k \cdot gcd(a,b)$

求解$ax+by=gcd(a,b)$

若$b=0$,那么令$x=1$，原方程可化为$a=c$,等式成立

我们知道
$$gcd(a,b)=gcd(b,a \% b)$$

那么我们设$t=\lfloor \frac ab \rfloor$。

$$gcd(a,b)=gcd(b,a-tb)$$

$$gcd(a,b)=by_1+(a-tb)x_1$$

$$gcd(a,b)=by_1+ax_1-tbx_1$$

$$gcd(a,b)=ax_1+b(y1-tx1)$$

类比：

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

得到：

$$x=x_1,y=y_1-tx_1$$

扩展欧几里得求逆元：

求逆元

$$t\; \bmod \; p= 1 $$

$$t + x \cdot p = 1$$

所以求$ax+by=1$的解。

$$\gcd(a,b)=1$$

质数

质数的定义这里不再重复。

判断一个数是不是素数

一个数的因子总是成对出现，所以我们判断质数时枚举到$\sqrt{n}$即可。

bool Is_prime(int n);
{
    if(n==1)return false;
    if(n==2||n==3||n==5||n==7)return true;
    for(register int i=2;i*i<=n;i++)
        if(n%i==0)return false;
    return true;    
}

筛法

埃氏筛

一个质数的倍数一定不是质数。


const int MAXN=1000010;
bool prime[MAXN];
void make_prime)()
{
    memset(prime,true,sizeof(prime));
    prime[0]=prime[1]=false;
    int t=sqrt(MAXN);
    for(register int i=2;i<=t;i++)
    {
        if(prime[i])
        {
            for(register int j=2*i;j<MAXN,j+=i)
            {
                prime[j]=false;
            }
        }
    }
    return;
}

欧拉筛

用prime[MAXN]标记一个数是不是素数，Prime[MAXN]表示质数有哪些。

如果我们发现prime[i]为真，那么存储质数的Prime[]就要存储进一个新数i。


const int MAXN=1000010;
bool prime[MAXN];
int Prime[MAXN];
int num=0;
void make_prime()
{
    memset(prime,true,sizeof(prime));
    prime[0]=prime[1]=false;
    for(int i=2;i<=MAXN;i++)
    {
        if(prime[i])
        {
            Prime[num++]=i;
        }
        for(int j=0;j<num&&i*Prime[j]<MAXN;j++)
        {
            prime[i*Prime[j]]=false;
            if(!(i%Prime[j]))
                break;
        }
    }
    return;
}

Miller-Rabin素数测试

//博主太菜了，还没有学，将尽快补充

组合数学

加法原理

如果做一件事$n$类方法，其中第$i$中有$m_i$种方法，则做这件事有$\sum m_i$种方法。

乘法原理

如果做一件事$n$个步骤，其中第$i$步有$m_i$方法，则做这件事有$\prod m_i$种方法。

容斥原理

//待补充

全排列

将$n$个元素排成一列的不同方案数为$n!$个。

运用乘法原理，可得
$$\prod_{i=1}^n i =n!$$

排列数

从$n$个元素中选择$k$个，排成一列，不同的方案数为：

相当于从$n$个元素中

$$A_n^k=\frac{n!}{(n-k)!}=C_n^k \times k!$$

组合数

从$n$个元素中选择$k$个，不同的方案数为:

$$C_n^k=\frac{A_n^k}{k!}=\frac{n!}{k!(n-k)!}$$

帕斯卡公式

$$C_n^k=C_{n-1}^k+C_{n-1}^{k-1} $$

线性递推公式

$$C_n^k=C_n^{k-1} \times \frac{n-k+1}{k}$$

这样我们就可以在$O(N)$的时间内求出$C_n^1$到$C_n^n$的结果了。

欧拉函数

//博主太菜了，还没有学，将尽快补充
upd:写完这篇博客之后决定去学以下欧拉函数

定义

老规矩了：

在数论中，对正整数n，欧拉函数是小于n的正整数中与n互质的数的数目（$\varphi(1)=1$） —-百度百科

~~这次好像能看懂了（雾~~

尽量讲的详细一点：

对于正整数$n$,欧拉函数是在$[0,n)$区间范围内$gcd(i,n)=1$(即于$n$互质的数)的数量。

记为$\varphi(n)$.

特别的$\varphi(1)=1$。

如何计算

通项公式：
$$\varphi(x)=x \times \prod_{i=1}^n (1-\frac{1}{p_i})$$
$$\varphi(1)=1$$

其中$p_1,p_2,p_3,\dots,p_n$为$x$的所有质因数，$x \in N^+$.

理解公式

我们知道，对于$x$的一个质因数$p_i$,在$[0,x)$以内是均匀分布的，所以$x$以内有$\frac{1}{p_i}$的数是$p_i$的倍数。

也就是说，有$1-\frac{1}{p_i}$的不是$p_i$的倍数。

同理，对于$p_j$，有$1-\frac{1}{p_j}$的数不是$p_i$的倍数。

所以说，有$(1-\frac{1}{p_i})(1-\frac{1}{p_j})$的数，既不是$p_i$的倍数，也不是$p_j$的倍数。

最后就有$\prod_{i=1}^n(1-\frac{1}{p_i})$的数和$x$互质，个数当然就是$x \times \prod_{i=1}^n (1-\frac{1}{p_i})$。

积性函数

这里只是简单说一下定义。

如果，当$a$和$b$互质时，$f(a \times b)=f(a) \times f(b)$,那么称$f()$是积性函数。

若对于任意的$a,b$，$f(a \times b)=f(a) \times f(b)$,那么称$f()$是完全积性函数。

性质

对于质数$p$，$\varphi(p)=p-1$。
若$p$是质数，$n=p^k$,则$\varphi(n)=p^k-p^{k-1}$.
欧拉函数是积性函数，但不是完全积性函数。
若$a$和$b$互质，$\varphi(a \times b)=\varphi(a) \times \varphi(b)$。
特别的，当$a=2$，$b$为奇数时，$\varphi(2n)=\varphi(n)$。
当$n>2$时，$\varphi(n)$为偶数。
小于$n$的数中，于$n$互质的数的总和为$\varphi(n) \times n /2(n > 1)$
$n = \sum_{d|n} \varphi(n)$.

代码实现

埃氏筛即可。
我们用$p[i]$表示$\varphi(i)$,可以一开始把$p[x]$赋值为$x$，然后每次找到它的质因数就$p[x]=p[x]/p[i] \times p[i]-1$

inline void Euler(int n){
	for(int i=1;i<=n;i++)p[i]=i;
	for(int i=2;i<=n;i++){
		if(p[i]==i){
			for(int j=i;j<=n;j+=i){
				p[i]=p[j]/i*(i-1);
			} 
		}
	}
}

欧拉定理

upd：在本机房其他成员在打比赛的同时，Herself32在学欧拉定理。
内容：
如果$gcd(a,m)=1$，$a^{\varphi(m)} \equiv 1(mod \; m)$

扩展？

当 $m$为质数的时候就是费马小定理.

扩展欧拉定理：

对于$gcd(a,m) \not = 1$,$a^b \equiv a^{min(b,b \;mod \;\varphi(m)+\varphi(m))}\;(mod \; m)$

证明？

不会。

阶和原根

阶

如果$gcd(a,m)=1$,记$x$为最小的正整数使得$a_x \equiv 1(mod \; m)$
那么称$x$是$a$模$m$的阶。
性质：$x|\varphi(m)$

原根

如果$g$在模$m$意义下的阶是$\varphi(m)$，那么称$g$是$m$的原根。

最后扔一下我的数论模板：

inline long long gcd(long long a,long long b){//O(log n)
	return (!b)?a:gcd(b,a%b);
}
inline long long lcm(long long a,long long b){//O(log n)
	return a/gcd(a,b)*b/gcd(a,b);
}
inline long long mod(long long a,long long b,long long p){
	return (a%p+b)%p;
}//O(1)
inline void ex_gcd(int a,int b,int &c,int &x,int &y){
	if(!b)c=a,x=1,y=0;
	else{
		ex_gcd(b,a%b,c,y,x);
		y-=x*(a/b);
	}
}
inline long long quick_power1(long long a,long long b,long long p){
	long long ans=1;
	for(;n;n>>=1,a=a*a%p)if(n&1)res=res*a%p;
	return res;
}//二进制快速幂 O(log n) 
inline long long quick_power2(long long a,long long b,long long p){
	if(n==0)return 1;
	if(n%2==0){
		long long x=quick_power2(a,n/2,p);
		return x*x%p;
	}
	else return a*quick_power2(a,n-1,p);
}//分治快速幂 O(log n) 
inline long long INV_ALL(long long a,long long long p){
	long long GCD,tmp,res;
	ex_gcd(a,p,GCD,res,tmp);
	return mod(res,p,p);
}
inline long long INV_PRIME(long long a,long long p){
	return quick_power1(a,p-2,p);
}
inline void Euler(){
	const int MAXN=1000010;
	bool prime[MAXN];
	int Prime[MAXN],num=0;
    memset(prime,true,sizeof(prime));
    prime[0]=prime[1]=false;
    for(int i=2;i<=MAXN;i++){
        if(prime[i])Prime[num++]=i;
        for(int j=0;j<num&&i*Prime[j]<MAXN;j++){
            prime[i*Prime[j]]=false;
            if(!(i%Prime[j]))break;
        }
    }
    return;
}//欧拉筛

幼儿园数论/数学学习笔记

模运算