lucas定理（lucas定理中p为什么要为素数）

本文目录

• lucas定理中p为什么要为素数
• 什么是Lucas定理
• 质数有哪些特性
• 概率c公式是什么 c表示什么
• 大数组合取模,Lucas定理,费马小定理的运用

lucas定理中p为什么要为素数

加快速幂解决。 #include #include typedef __int64 lld; c***t lld MAX=500005; bool ok,c=0; lld count(lld n,lld prime) { lld ret=0; while(n/prime) { ret+=n/prime; n/=prime; } return ret; ...

什么是Lucas定理

• LUCAS就是光。光的定理。

• 陈冠希+张柏芝=Lucas

• 就是谢霆锋他儿子。

质数有哪些特性

质数（prime number）又称素数，有无限个。一个大于1的自然数，除了1和它本身外，不能被其他自然数（质数）整除，换句话说就是该数除了1和它本身以外不再有其他的因数.比如：2,3,5,7,11，...等。

质数的个数是无穷的。欧几里得的《几何原本》中有一个经典的证明。它使用了证明常用的方法：反证法。具体证明如下：假设质数只有有限的n个，从小到大依次排列为p1，p2，……，pn，设N=p1×p2×……×pn，那么，  是素数或者不是素数。如果  为素数，则  要大于p1，p2，……，pn，所以它不在那些假设的素数集合中。

1、如果 为合数，因为任何一个合数都可以分解为几个素数的积；而N和N+1的最大公约数是1，所以不可能被p1，p2，……，pn整除，所以该合数分解得到的素因数肯定不在假设的素数集合中。因此无论该数是素数还是合数，都意味着在假设的有限个素数之外还存在着其他素数。所以原先的假设不成立。也就是说，素数有无穷多个。

2、其他数学家给出了一些不同的证明。欧拉利用黎曼函数证明了全部素数的倒数之和是发散的，恩斯特·库默的证明更为简洁，哈里·弗斯滕伯格则用拓扑学加以证明。

扩展资料：

尽管整个素数是无穷的，仍然有人会问“100，000以下有多少个素数？”，“一个随机的100位数多大可能是素数？”。素数定理可以回答此问题。

1、在一个大于1的数a和它的2倍之间（即区间（a, 2a]中）必存在至少一个素数。

2、存在任意长度的素数等差数列。 

3、一个偶数可以写成两个合数之和，其中每一个合数都最多只有9个质因数。

4、一个偶数必定可以写成一个质数加上一个合成数，其中合数的因子个数有上界。

5、一个偶数必定可以写成一个质数加上一个最多由5个因子所组成的合成数。后来，有人简称这结果为 （1 + 5）

6、一个充分大偶数必定可以写成一个素数加上一个最多由2个质因子所组成的合成数。简称为 （1 + 2） 

质数被利用在密码学上，所谓的公钥就是将想要传递的信息在编码时加入质数，编码之后传送给收信人，任何人收到此信息后，若没有此收信人所拥有的密钥，则解密的过程中（实为寻找素数的过程），将会因为找质数的过程（分解质因数）过久，使即使取得信息也会无意义。

在汽车变速箱齿轮的设计上，相邻的两个大小齿轮齿数设计成质数，以增加两齿轮内两个相同的齿相遇啮合次数的最小公倍数，可增强耐用度减少故障。

在害虫的生物生长周期与杀虫剂使用之间的关系上，杀虫剂的质数次数的使用也得到了证明。实验表明，质数次数地使用杀虫剂是最合理的：都是使用在害虫繁殖的**期，而且害虫很难产生抗药性。

以质数形式无规律变化的导弹和鱼雷可以使敌人不易拦截。

多数生物的生命周期也是质数（单位为年），这样可以最大程度地减少碰见天敌的机会。

随机素性测试的基本结构：

1、随机选取一个数字a。

2、检测某个包含a和输入n的等式（与所使用的测试方法有关）。如果等式不成立，则n是合数，a作为n是合数的证据，测试完成。

3、从1步骤重复整个过程直到达到所设定的精确程度。

在几次或多次测试之后，如果n没有被判断为合数，那么我们可以说n可能是素数。

常见的检测算法：费马素性检验（Fermat primality test），米勒拉宾测试（Miller–Rabin primality test） ，Solovay–Strassen测试，卢卡斯-莱默检验法（Lucas–Lehmer primality test）。

概率c公式是什么 c表示什么

概率公式：C(n,k)=n(n-1)(n-2)...(n-k+1)/k!，其中k≤n。C表示组合数。

概率公式是什么 c表示什么

C表示组合数。

C(n,m) 表示n选m的组合数，其中n是下标 , m是上标 (C上面m,下面n)。

nCk是一个整体，是n个元素中，取k个元素的取法的个数，也叫n个元素中，取k

个k组合数，（C代表组合），算法是：

nCk＝n!/k!（n-k）!＝n（n-1）……（n-k+1）/k!

等于从n开始连续递减的m个自然数的积除以从1开始连续递增的m个自然数的积。

该概率公式的推导过程：

在这个证明中，表示n次实验中，成功的k次，取法的个数。

每次取定后，k次成功，n-k次失败，概率用乘法P＝p^k*(1-p)^(n-k)

总共有nCk个取法，即nCk个情况，概率用加法，每个情况的概率又相同，所以

成为nCk倍。

求组合数C的方法

1、当n,m都很小的时候可以利用杨辉三角直接求。

C(n,m)=C(n-1,m)+C(n-1,m-1)；

2、利用乘法逆元

乘法逆元：(a/b)%mod=a*(b^(mod-2)) mod为素数。

逆元可以利用扩展欧几里德或欧拉函数求得。

3、当n和m比较大，mod是素数且比较小的时候（10^5左右），通过Lucas定理计算

大数组合取模,Lucas定理,费马小定理的运用

从一个例题：【HDU 3037】 Saving Beans 来开始Lucas定理的应用。 题目大意为：松鼠要从n棵树上摘一共m个豆子，结果的方案数对素数p（不大于1e5）取模，求解。 思路： 可以理解为m个豆子分为n份，求分的方法个数。 由插板法来对m个数进行划分，由于可能某棵树没有摘豆子，可以理解为：x1+x2+x3+……+xn=m的解的个数，即为C(m+n-1,n-1)。（将m颗豆子加上n-1个板子的位置，得到的序列再从中取n-1个板子的位置）=C(m+n-1,m)。 由于m的值取0~m，那么就得sum=C(n-1,0)+C(n,1)+C(n+1,2)+C(n+2,3)+……+C(m+n-1,m)。 利用公式C（n，r）=C（n-1，r）+C（n-1，r-1）=C（n-1，r）+C（n-2，r-1）+C（n-3，r-2）…… sum=C（n+m，m）。 也就是说，接下来的算法变成了C（n+m，m）%p。 然后就是Lucas定理的运用： Lucas（m，n，p）=C（m%p，n%p，p）✲Lucas（m/p，n/p，p）。 Lucas（x，0，p）=1。 这里可以采用的方法是递归求解。 简单的理解就是： 以求解n! % p 为例，把n分段，每p个一段，每一段求得结果是一样的。但是需要单独处理每一段的末尾p,2p,...,把p提取出来，会发现剩下的数正好又是(n/p)! ，相当于划归了一个子问题，这样递归求解即可。 这个是单独处理n！的情况，当然C(n,m)就是n！/(m! *（n－m）！），每一个阶乘都用上面的方法处理的话，就是Lucas定理了. Lucas最大的数据处理能力是p在10^5左右。 而C(a,b) =a! / ( b! ✲ (a-b)! ) mod p 其实就是求 ( a! / (a-b)!) ✲ ( b! )^(p-2) mod p

上面这一步变换是根据费马小定理：假如p是质数，且a,p互质，那么a的（p-1）次方除以p的余数恒为1, 那么a和a^(p-2)互为乘法逆元，则（b / a) = (b * a^(p-2) ) mod p)

b!与b! (p-2)互为乘法逆元，即b!✲b! (p-2)=1，那么，

//快速幂a^b % k

//求C(n, m)%p p最大为10^5 n, m可以很大！

用下面的Lucas定理程序实现就能得出结果，实现过程中要注意乘法时的强制转换