Don't let your dreams be dreams.

WELCOME——一只蒟蒻的幻想

| 笔记, 数论

数论入门知识整理

整理一下初等数论的基础知识。。

今天听狄拉克(贱贱)神犇给初三讲课。见证了我旁边的初三爷从茫然到一脸懵逼到崩溃的全过程，据他讲述，这是他至今为止唯一一次完全没有听懂的讲课。

好这些都不是重点
让我们来理一下重点是什么:

逆元

关于逆元是什么,讲课的时候我给刚才那位当时还是处在茫然状态的初三爷讲了一下,然后结果是他没有听懂.讲道理逆元有这么难吗!!
对于$a\cdot b\equiv1(mod\ P)$我们就称b为a在模P域下的逆元,记a的逆元为$a^{-1}$(逆元要在模域下才有意义!!)
逆元有什么用呢？对于在模域下的除法$\frac{a}{b}\equiv a\cdot b^{-1}(mod\ P)$
怎么求逆元？
首先对于在模P域下的a,存在逆元的条件是$gcd(a,P)=1$
当a存在逆元时根据欧拉定理可得$a^{-1}\equiv a^{\phi(P)-1}(mod\ P)$
然后使用快速幂就可以在log的时间内求出单个元素的逆元了
如何快速求1~n所有数的逆元(这里的条件是P为素数)?
设$P\div a=q…r$即$P=qx+r$
然后可以将其放到模域下
\begin{align}
P & = qx+r \\
0 & \equiv qx+r (mod\ P) \\
-r & \equiv qx(mod\ P) \\
-rq^{-1} & \equiv x(mod\ P) \\
x^{-1} & \equiv -qr^{-1}(mod\ P) \\
x^{-1} & \equiv -\lfloor\frac{P}{x}\rfloor\cdot (P\ mod\ x)^{-1}(mod\ P)
\end{align}
然后就可以O(n)递推了
Back to menu

扩展欧几里得

第一个问题。。欧几里得算法是什么..其实就是辗转相除求GCD。。
那么扩展欧几里得是什么呢？
扩展欧几里得用来解决一类$a\cdot x+b\cdot y=c$的问题，可以求x的最小正整数解。当这个方程有解的时候，我们可以得知$gcd(a,b)|a$,$gcd(a,b)|b$,所以$gcd(a,b)|a\cdot x,gcd(a,b)|b\cdot y$，所以$gcd(a,b)|c$.然后可以把原方程化为$a\cdot x+b\cdot y=gcd(a,b)$求出解以后再乘上一个$c/gcd(a,b)$就可以了
对于怎么求解这个方程呢？
设$A=b,B=a\%b$
将原方程化为$A\cdot x_0+B\cdot y_0=gcd(a,b)$,也就是$b\cdot x_0+(a\%b)\cdot y_0=gcd(a,b)$
假设我们已经求出了这个方程，那么我们怎么推得原来方程的解呢?
\begin{align}
b\cdot x_0+(a\%b)\cdot y_0 & = gcd(a,b) \\
b\cdot x_0+(a-\lfloor\frac{a}{b}\rfloor\cdot b)\cdot y_0 & = gcd(a,b) \\
b\cdot x_0+a\cdot y_0-b\cdot\lfloor\frac{a}{b}\rfloor\cdot y_0 & = gcd(a,b) \\
a\cdot y_0+b\cdot(x_0-\lfloor\frac{a}{b}\rfloor\cdot y_0) & = gcd(a,b)
\end{align}然后我们就可以知道$x=y_0,y = x_0-\lfloor\frac{a}{b}\rfloor\cdot y_0$。
然后我们只要对原方程每次这样递归下去，然后就可以求出原方程的解了。

代码也很简单

1
2
3
4
5
int Exgcd(int a,int b,int &x,int &y){
	if (b==0) {x = 1;y = 0;return;}
	Exgcd(b,a%b,x,y);
	int tmp = x;x = y;y = tmp-(a/b)*y;
}

Back to menu

欧拉筛法

对于筛法我最先知道的是NlogN的倍增筛质数，原来感觉这么一个东西应该就够了。有些题目只能放O(N)过，觉得这个东西越来越没用确实没用。
欧拉筛法是什么呢？
欧拉筛法可以用来O(n)的时间里筛大部分（还是全部？并不清楚）积性函数。
什么是积性函数？
积性函数：任取p，q且$gcd(p,q)=1$，若$f(xy)=f(x)f(y)$，则f是一个积性函数
完全积性函数：任取p,q，若$f(pq)=f(p)f(q)$，则f是一个完全积性函数
欧拉筛法怎么做呢？
从2~n枚举一个数i，然后枚举小于i的质数j。如果j不是i的因子，那么j就是i*j的最小质因子，然后可以计算出f(i*j)的值。当j|i时，j是i的最小质因子，对于之后的所有质数k，i*k的最小质因子都不是k，而是j，所以直接跳出循环。这样我们可以发现每一个数都只被它的最小质因子筛到一次，所以整个算法的复杂度是O(n)的。

欧拉筛素数代码

1
2
3
4
5
6
7
8
9
void Getprime(){
	for (int i=2;i<=n;i++){
		if (!vis[i]) prime[++sum] = i;
		for (int j=1;j<=sum && i*prime[j]<=n;j++){
			vis[i*prime[j]] = j;
			if (i%prime[j]==0) break;
		}
	}
}

Back to menu

中国剩余定理(CRT)

中国剩余定理，用来解决一类一元线性同余方程组
一元线性同余方程组问题最早可见于中国南北朝时期（公元5世纪）的数学著作《孙子算经》卷下第二十六题，叫做“物不知数”问题，原文如下：
有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？
即，一个整数除以三余二，除以五余三，除以七余二，求这个整数。《孙子算经》中首次提到了同余方程组问题，以及以上具体问题的解法，因此在中文数学文献中也会将中国剩余定理称为孙子定理。
宋朝数学家秦九韶于1247年《数书九章》卷一、二《大衍类》对“物不知数”问题做出了完整系统的解答。明朝数学家程大位将解法编成易于上口的《孙子歌诀》：三人同行七十希，五树梅花廿一支，七子团圆正半月，除百零五使得知这个歌诀给出了模数为3、5、7时候的同余方程的秦九韶解法。意思是：将除以3得到的余数乘以70，将除以5得到的余数乘以21，将除以7得到的余数乘以15，全部加起来后除以105，得到的余数就是答案。比如说在以上的物不知数问题里面，按歌诀求出的结果就是23.（以上摘自某谋财害命网站）
然后把上面乱七八糟的东西整理一下就是求满足
\begin{align}
x & \equiv a_1(mod\ b_1) \\
x & \equiv a_2(mod\ b_2) \\
& . \\
& . \\
x & \equiv a_n(mod\ b_n)
\end{align}的最小x的值
这个方程是一定存在解的吗？
如果$a_1\ mod\ gcd(b_1,b_2)\not=a_2\ mod \ gcd(b_1,b_2)$,那么原方程组没有解
对于有解的方程
我们设$$M=\prod_{i=1}^{n} b_i$$$$D_i=\frac{M}{b_i}$$对于每一个方程，求出$$D_ix\equiv 1 (mod\ b_i)$$我们用求逆元的方法解出x，并把$D_i\cdot x$记为$X_i$
那么$X_i\cdot a_i$对其他所有b模的结果都为0，且对于模$b_i$的结果为$a_i$
那么$(\Sigma_{i=1}^{n} X_i\cdot A_i)mod M$就是答案
Back to menu

组合数

一些比较常见的性质
$$A_{n}^{m}=C_{n}^{m}\cdot m!$$$$C_{n}^{m}=C_{n}^{n-m}$$$$C_{n}^{m}=C_{n-1}^{m}+C_{n-1}^{m-1}$$$$\sum_{i=0}^{n} C_{n}^{i}=2^n$$恩其他的应该没有什么好写的
Back to menu

Lucas定理，组合数取模

lucas定理用来计算$C_{n}^{m}\ mod \ P$的问题，其中P为质数，如果P不是质数就要用CRT进行合并。$$Lucas:C_{m}^{n} \equiv C_{m\ mod\ P}^{n\ mod\ P}\cdot C_{m/P}^{n/P}\ mod\ P$$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <cstring>
#include <cstdio>
using namespace std;
typedef long long LL;
LL n,m,p;
LL ksm(LL a,LL k){
    LL res = 1;
    for (;k;k>>=1,a=a*a%p) if (k&1) res = res*a%p;
    return res;
}
LL C(LL n,LL m){
    if(m>n)return 0;
    LL ans=1;
    for(int i=1;i<=m;i++){
        LL a=(n+i-m)%p;
        LL b=i%p;
        ans=ans*(a*ksm(b,p-2)%p)%p;
    }
    return ans;
}
LL Lucas(LL n,LL m){
    if(m==0)return 1;
    return C(n%p,m%p)*Lucas(n/p,m/p)%p;
}
int main(){
    scanf("%d",&T);
    scanf("%lld%lld%lld",&n,&m,&p);
    printf("%lld\n",Lucas(n,m));
}

Back to menu

有错误请指出$$\mathcal{FIN.}$$