错排问题 什么是错排问题 若有n个人，都想给其他n-1个人中的任意一个送信（当然不能送给自己），请问一共有多少种送法？ 建模 对于一个具体的题目，数学上喜欢抽象，于是可以把这样的问题抽象为一个数学模型，下面给出定义 对于n个元素，若一个排列中所有的元素都不在自己原来的位置上，那么这样的排列就叫原排列的一个错排，n个元素的错排数记为D(n)。研究一个排列的错排个数的问题，就叫做错排问题或...

Lucas定理 Lucas定理详述 内容 对于一个组合数CmnC_m^nCmn​，取模一个素数ppp的值，假设n=a×p+bn=a\times p+bn=a×p+b,m=c×p+dm=c\times p+dm=c×p+d有： Cnm≡Cac×Cbd(mod  p)C_n^m≡C_a^c\times C_b^d(\mod p)Cnm​≡Cac​×Cbd​(modp) 证明 先证明一个一会...

数论四大定理 Ⅰ.威尔逊定理 Ⅱ.欧拉定理 Ⅲ.孙子剩余定理 Ⅳ.费马小定理 威尔逊定理 内容 若一个数p为素数的充要条件为:p可以整除(p+1)!+1(p+1)!+1(p+1)!+1 证明 充分性 证明定理的充分性，则只要证明当p可以整除(p+1)!+1(p+1)!+1(p+1)!+1时，p为素数。 考虑到从正面直接证明不太好证明，则考虑使用反正法，也就是证明该命题的逆否命题，...

​ 内容 孙子定理也叫中国剩余定理，也就是Chinese remainder theorem，简称CRT，是中国古代求解一次线性同余方程组的方法，最早源于南北朝时期的数学著作《孙子算经》中的一到叫“物不知数”的问题，原文如下： 有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？即，一个整数除以三余二，除以五余三，除以七余二，求这个整数。《孙子算经》中首次提到了同余方程组问题...

数论四大定理 Ⅰ.威尔逊定理 Ⅱ.欧拉定理 Ⅲ.孙子剩余定理 Ⅳ.费马小定理 欧拉定理 内容 对于整数n,a且n,a互质则有 aφ（n）≡1（mod  n）a^{φ（n）}≡ 1（\mod n）aφ（n）≡1（modn） 其中φ（n）φ（n）φ（n）为n的欧拉函数值 欧拉函数 百度百科 φ(n)φ(n)φ(n)为小于n的正整数种与n互质的数的数目。 证明 要证aφ(n)≡1（mod...

​ 斐蜀定理 内容 斐蜀定理又叫贝祖定理，它的内容是这样的： 若a,b∈Na,b\in Na,b∈N,那么对于任意x，y，方程ax+by=gcd(a,b)∗k(k∈N)ax+by=gcd(a,b)*k(k\in N)ax+by=gcd(a,b)∗k(k∈N)一定有解，且一定有一组解使ax+by=gcd(a,b)ax+by=gcd(a,b)ax+by=gcd(a,b) 推论 a，b互素的...

逆元的理解 数论中的逆元即数论倒数，既一个正整数a，存在另一个正整数x使得a×x≡1(mod  p)a\times x≡1(\mod p)a×x≡1(modp)（其中a与p互素），则称x为a的一个关于p的逆元。 逆元的由来 为什么要有逆元这个说法呢，类比到矩阵中去，在矩阵乘法中，两个乘积为单位矩阵的矩阵，其中一个矩阵就是另一个矩阵的逆矩阵，这样就解决了矩阵中没有定义除法的问题。 而类似的...

唯一分解定理初探 唯一分解定理，又叫算术基本定理 内容 她的内容是: 任何一个大于1的自然数N，如果N不为素数，那么，N就能被唯一的分解为有限个素数的乘积。 公式 N=p1a1×p2a2×p3a3×…×pnanN=p_1^{a_1}\times p_2^{a_2}\times p_3^{a_3}\times … \times p_n^{a_n}N=p1a1​​×p2a2​​×p3a3​...

关于数论 数论是纯粹数学的分支，主要研究整数的性质，而数论又分为初等数论和高等数论，其中我们研究的方向是初等数论 规范 由于数论是研究整数数学，所以今后使用的未知数都有一个隐含条件x∈Nx \in Nx∈N 素数 聊到整数就免不了谈素数，数论种素数的定义大家小学的时候都学过，所谓素数，就是因子只有1和它本身的数，最小的素数是2。 素数判定 下面有这样一个问题，任意给定一个x,请判断这...

关于幂 所谓幂，就是当计算m个n相乘时，即nmn^mnm时，n的指数，所谓幂运算就是指针对幂的运算。 求次方 现在给定n和m，请求出nmn^mnm，那么，首先想到的当然时cmath中提供的pow()函数，既简单又轻便，但是我们知道，这个函数的参数和返回值都是double类型的，精度可能会有误差，或者当需要计算的数很大(通常题目会要求取模一个比较小的数)时（具体之后谈），采用这个直接的方法...