精华内容
下载资源
问答
  • 费马小定理求逆元

    2017-06-16 11:34:07
    逆元一般用扩展欧几里得算法来求得,如果为素数,那么还可以根据费马小定理得到逆元为。   推导过程如下 因此逆元为a^(m-2)%m,用快速幂。代码如下:#include #include using namespace std; typedef long ...

    对于正整数,如果有,那么把这个同余方程中的最小正整数解叫做的逆元。

     

    逆元一般用扩展欧几里得算法来求得,如果为素数,那么还可以根据费马小定理得到逆元为

     

    推导过程如下

    因此逆元为a^(m-2)%m,用快速幂求。代码如下:

    #include<iostream>
    #include<cmath>
    using namespace std;
    typedef long long LL;
    LL quick_mod(LL a,LL b,LL m) //快速幂求a^b%m; 
    {
    	LL ans=1;
    	while(b)
    	{
    		if(b&1) ans=ans*a%m;
    		b>>=1;
    		a=a*a%m;
    	}
    	return ans;
    }
    int main()
    {
    	LL a,b,m;//m为素数
    	cin>>a>>m;
    	cout<<quick_mod(a,m-2,m)<<endl;
    	return 0;
    }

    展开全文
  • 费马小定理求逆元(不知详不详细,毕竟我只是一个蒟蒻)

    首先:逆元定义

    我们先说明一下什么是逆元
    逆元是指,在模PP的意义下,aaxx的积模PP后等于1
    式子:ax1a*x≡1 (mod(mod P)P)

    其次:费马小定理

    有了逆元的定义后,我们引入一下费马小定理
    何为费马小定理?
    如果pp是一个质数,而整数aa不是pp的倍数,则有ap11(mod p)a^{p-1}≡1(mod\ p)

    略证:

    两个引理
    引理1
    abca,b,c为任意3个整数,mm为正整数,且(m,c)=1(m,c)=1,则当acbc(mod m)a·c≡b·c(mod\ m)时,有ab(mod m)a≡b(mod\ m)
    证明:acbc(mod m)a·c≡b·c(mod\ m)可得acbc0(mod m)ac–bc≡0(mod\ m)可得(ab)c0(mod m)(a-b)·c≡0(mod\ m)。因为(m,c)=1(m,c)=1m,cm,c互质,cc可以约去,ab0(mod m)a–b≡0(mod\ m)可得ab(mod m)a≡b(mod\ m)
    引理2
    mm是一个整数且m>1m>1bb是一个整数且(m,b)=1(m,b)=1。如果a[1],a[2],a[3],a[4],a[m]a[1],a[2],a[3],a[4],…a[m]是模mm的一个完全剩余系,则ba[1],ba[2],ba[3],ba[4],ba[m]b·a[1],b·a[2],b·a[3],b·a[4],…b·a[m]也构成模mm的一个完全剩余系。
    证明:若存在2个整数ba[i]b·a[i]ba[j]b·a[j]同余即ba[i]ba[j](mod m)..(i>=1j>=1)b·a[i]≡b·a[j](mod\ m)..(i>=1 且 j>=1),根据引理1则有
    a[i]a[j](mod m)a[i]≡a[j](mod\ m)。根据完全剩余系的定义可知这是不可能的,因此不存在2个整数ba[i]b·a[i]ba[j]b·a[j]同余
    所以ba[1],ba[2],ba[3],ba[4],ba[m]b·a[1],b·a[2],b·a[3],b·a[4],…b·a[m]构成模mm的一个完全剩余系。
    证明费马小定理
    构造素数 的完全剩余系
    P={1,2,3,...,p1}.P=\{1,2,3,...,p-1\}.
    因为(a,p)=1(a,p)=1,由引理2可得
    A={a,2a,3a,...,(p1)a}A=\{a,2a,3a,...,(p-1)a\}
    也是pp的一个完全剩余系。由完全剩余系的性质,
    1×2×3×...×(p1)a2a3a...(p1)a(mod p)1×2×3×...×(p-1)≡a·2a·3a·...·(p-1)a(mod\ p)
    (p1)!(p1)!ap1(mod p)(p-1)!≡(p-1)!·a^{p-1}(mod\ p)
    易知((p1)!,p)=1((p-1)!,p)=1,同余式两边可约去(p1)!(p-1)!,得到
    ap11(mod p)a^{p-1}≡1(mod\ p)
    这样就证明了费马小定理。

    上述均来自百度百科

    最终:费马小定理求逆元

    现在我们手上有两个式子
    一是逆元:ax1a*x≡1 (mod(mod P)P)
    二是费马小定理:aP11a^{P-1}≡1 (mod(mod P)P)
    诶,这两个式子是不是有点想
    我们把费马小定理的式子转一下
    aP11(mod P)aaP21(mod P)a^{P-1}≡1 (mod\ P)变为a*a^{P-2}≡1(mod\ P)
    此时再和逆元的式子对比一下
    发现:似乎,xx就是aP2a^{P-2}
    自信点,把似乎去掉
    至此,我们就知道了,在P是质数时aa在模PP的意义下的逆元就是aP2a^{P-2}
    大功告成
    切记,只有模数PP是质数的情况下才可以用费马小定理求逆元
    顺便说一下,求aP2a^{P-2}可以用快速幂

    展开全文
  • 组合数算法简述:杨辉三角形+拓展欧几里得求逆元+费马小定理求逆元+阶乘逆元递推组合数基本公式杨辉三角形法逆元法-1.拓展欧几里得求逆元-2.费马小定理求逆元-3.阶乘逆元递推-4.逆元法组合数取模总结模板 前言:  ...

    前言:
      在很多问题中都需要计算组合数,在小规模计算中我们可以直接使用组合数公式稍加算法优化进行计算,但在大规模取模计算时往往需要更加快速的算法,接下来主要介绍杨辉三角形法逆元法(拓欧和费马小定理俩种方法)以及在逆元的基础上进行的阶乘逆元递推优化法

    组合数基本公式

    C(n,m) = n! / m!(n-m)!
    在这里插入图片描述

    杨辉三角形法

    在这里插入图片描述
      如图是杨辉三角形(帕斯卡三角),是二项式系数在三角形中的几何排列,可以得出一个组合数的规律,具体到公式便是:

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

      由此可以通过一个C_arr数组做一个dp打表得到一定范围内的组合数。

    算法特点:

    • 算法复杂性=O(n2)
    • 数据范围适合在1000以内,尽量不要大于10000.
    • 无特殊要求

    算法模板:

    //方法一:杨辉三角打表法,适合n,m规模均较小,一般适用于1000以内,尽量不超过10000,O(n^2)
    //原理: C(n, m) = C(n-1, m) + C(n-1, m-1)
    //首先预处理打表数组,每个元素都对应一个组合数C(n,m)
    ll C_arr[MAXN + 10][MAXN + 10];
    //数据规模n,取模p
    void C_init(int n, int p) {
    	for (int i = 0; i <= n; i++) {
    		C_arr[i][0] = C_arr[i][i] = 1;
    		for (int j = 1; j < i; j++)
    			C_arr[i][j] = (C_arr[i - 1][j - 1] + C_arr[i - 1][j]) % p;
    	}
    }
    ll C(int n, int m) {
    	return C_arr[n][m];
    }
    

    逆元法

    逆元是什么:

    简单来说,逆元是数论模意义中的倒数,
    如a是b模p的逆元,即 a * b = 1(mod p),则k / a = k * b(mod p)。

    逆元在求组合数中的作用:

    由于组合数公式 C(n,m) = n! / m!(n-m)! 中 分母过大不方便操作,便可利用逆元化除为乘。
    转化为:

    C(n,m) mod p= (n!/m!(n-m)!) mod p = n!*inv(m!)*inv((n-m)!) mod p

    那么怎么求逆元呢,接下来主要介绍拓展欧几里得法和费马小定理法


    -1.拓展欧几里得求逆元

    拓展欧几里得算法:
    既可以求出最大公约数,还可以顺带求解出使得: ax + by = gcd(a,b) 的特解 x 和 y
    如何求出逆元:
    当a,b互质时,gcd(a,b)=1,两边同时mod b后得a*x=1(mod b),即x是a模b的逆元
    算法模板:

    //欧几里得算法:(这里用不到,仅仅是列出来做个对比)
    int gcd(int a, int b)
    {
    	if (a < b) swap(a, b);
    	return b == 0 ? a : gcd(b, a % b);
    }
    //拓展欧几里得算法:
    ll exgcd(ll a, ll b, ll& x, ll& y)//返回ab最大公因数,x为a%b逆元
    {
    	if (!b)
    	{
    		x = 1; y = 0;
    		return a;  //到达递归边界,返回上一层
    	}
    	ll r = exgcd(b, a % b, x, y);
    	ll temp = y;    //把x y回归上一层
    	y = x - (a / b) * y;
    	x = temp;
    	return r;     //得到a b的最大公因数
    }
    //求a%b的逆元
    ll calInv1(ll a, ll b) {
    	ll x, y;
    	ll g = exgcd(a, b, x, y);
    	if (g != 1) return -1;//a、b互质要求不满足
    	return (x % b + b) % b;
    }
    
    

    -2.费马小定理求逆元

    费马小定理:
    假如p是质数(这里强调p为质数,否则无效),且gcd(a,p)=1,
    那么:

    a^(p-1)≡1(mod p)。

    如何求出逆元:
    变形:

    a(p-2)≡a-1(mod p)

    即a(p-2)是a%p的逆元。

    算法模板:
    首先需要用到快速幂算法:

    //利用快速幂可以用来快速求a^(p-2)
    ll qpow(ll base, ll power, ll mod)
    {
    	ll ans = 1;
    	base %= mod;
    	while (power > 0) {
    		if (power & 1) {//指数为奇数,先乘
    			ans = ans * base % mod;
    		}
    		power >>= 1;//指数取半
    		base = (base * base) % mod;//基数平方
    	}
    	return ans;
    }
    

    然后利用快速幂即可得到逆元

    //求a%p的逆元
    ll calInv2(ll a, ll p)
    {
    	return qpow(a, p - 2, p);
    }
    

    -3.阶乘逆元递推

      在前法的基础上递推计算阶乘的逆元(需要连续大量计算阶乘的逆元时可能需要这么写)

    递推性质:
    设finv[]数组,finv[x] 表示 x! 的逆元 inv(x!)
    通过逆元的性质可以得到反向递推式:

    finv[i] = finv[i + 1] * (i + 1) % p

    然后我们就知道了所有阶乘的逆元,这样再套到组合数公式的逆元变形中:

    C(n,m) mod p= (n!/m!(n-m)!) mod p = n!*inv(m!)*inv((n-m)!) mod p

    并在此之前我们对阶乘设立一个数组并且初始化(阶乘数组fac[],fac[x]表示x!)

    fac[i] = fac[i - 1] * i % p;

    最后的组合数公式为:

    C(n,m) % p = fac[n] * finv[m] % p * finv[n-m] % p;

    算法模板:

    //阶乘逆元递推初始化
    void init(ll p)
    {
    	//阶乘数组初始化
    	fac[0] = 1;
    	for (int i = 1; i <= MAXN; i++)
    		fac[i] = fac[i - 1] * i % p;
    	finv[0] = 1;
    	//阶乘的逆元数组初始化
    	finv[MAXN] = calInv2(fac[MAXN], p);
    	for (int i = MAXN - 1; i > 0; i--)
    		finv[i] = finv[i + 1] * (i + 1) % p;//阶乘逆元反向递推式
    }
    //组合数C(n,m)取模p
    ll C(ll n, ll m, ll p)
    {
    	if (n < m)
    		return 0;
    	return fac[n] * finv[m] % p * finv[n - m] % p;
    }
    

    -4.逆元法组合数取模总结模板

    把前面的内容综合起来,就可以拿去做一个完整的组合数取模算法

    (1)不使用递推式的算法模板

    • 拓展欧几里得法
    #include<iostream>
    #include<algorithm>
    using namespace std;
    typedef long long ll;
    const ll MOD = 1e9 + 7;//模取1e9+7
    const int MAXN = 1000;//组合数n和m的范围暂且取1000
    ll fac[MAXN + 10];//阶乘数组
    //拓展欧几里得算法
    //返回ab最大公因数,x为a%b逆元
    ll exgcd(ll a, ll b, ll& x, ll& y)
    {
    	if (!b)
    	{
    		x = 1; y = 0;
    		return a;  //到达递归边界开始向上一层返回
    	}
    	ll r = exgcd(b, a % b, x, y);
    	ll temp = y;    //把x y变成上一层的
    	y = x - (a / b) * y;
    	x = temp;
    	return r;     //得到a b的最大公因数
    }
    //求a%b的逆元
    ll getInv(ll a, ll b) {
    	ll x, y;
    	ll g = exgcd(a, b, x, y);
    	if (g != 1) return -1;//a、b互质要求不满足
    	return (x % b + b) % b;
    }
    //阶乘数组初始化
    void fac_init(ll p)
    {
    	int i;
    	fac[0] = 1;
    	for (i = 1; i <= MAXN; i++)
    	{
    		fac[i] = fac[i - 1] * i % p;
    	}
    }
    //组合数函数C(n,m)取模p
    ll C(ll n, ll m, ll p)
    {
    	if (n < m)
    		return 0;
    	return fac[n] * getInv(fac[m], p) % p * getInv(fac[n - m], p) % p;
    }
    
    
    
    • 费马小定理法
    #include<iostream>
    #include<algorithm>
    using namespace std;
    typedef long long ll;
    const ll MOD = 1e9 + 7;//模取1e9+7
    const int MAXN = 1000;//组合数n和m的范围暂且取1000
    ll fac[MAXN + 10];//阶乘数组
    //快速幂base^power % mod
    ll qpow(ll base, ll power, ll mod)
    {
    	ll ans = 1;
    	base %= mod;
    	while (power > 0) {
    		if (power & 1) {//指数为奇数,先乘
    			ans = ans * base % mod;
    		}
    		power >>= 1;//指数取半
    		base = (base * base) % mod;//基数平方
    	}
    	return ans;
    }
    //求a%p的逆元
    ll getInv(ll a, ll p)
    {
    	return qpow(a, p - 2, p);
    }
    //阶乘数组初始化
    void fac_init(ll p)
    {
    	int i;
    	fac[0] = 1;
    	for (i = 1; i <= MAXN; i++)
    	{
    		fac[i] = fac[i - 1] * i % p;
    	}
    }
    //组合数函数C(n,m)取模p
    ll C(ll n, ll m, ll p)
    {
    	if (n < m)
    		return 0;
    	return fac[n] * getInv(fac[m], p) % p * getInv(fac[n - m], p) % p;
    }
    

    (2)使用递推式的算法模板

    这里逆元用费马小定理配合快速幂求:

    #include<iostream>
    #include<algorithm>
    using namespace std;
    typedef long long ll;
    const ll MOD = 1e9 + 7;//模取1e9+7
    const int MAXN = 1000;//组合数n和m的范围暂且取1000
    ll fac[MAXN + 10];//阶乘数组
    ll finv[MAXN + 10];//阶乘逆元数组
    
    //快速幂base^power % mod
    ll qpow(ll base, ll power, ll mod)
    {
    	ll ans = 1;
    	base %= mod;
    	while (power > 0) {
    		if (power & 1) {//指数为奇数,先乘
    			ans = ans * base % mod;
    		}
    		power >>= 1;//指数取半
    		base = (base * base) % mod;//基数平方
    	}
    	return ans;
    }
    //求a%p的逆元
    ll getInv(ll a, ll p)
    {
    	return qpow(a, p - 2, p);
    }
    //阶乘数组和阶乘的逆元数组初始化
    void init(ll p)
    {
    	//阶乘数组初始化
    	fac[0] = 1;
    	for (int i = 1; i <= MAXN; i++)
    		fac[i] = fac[i - 1] * i % p;
    	finv[0] = 1;
    	//先求出最大值的逆元作为递推基
    	finv[MAXN] = getInv(fac[MAXN], p);
    	//阶乘逆元反向递推式
    	for (int i = MAXN - 1; i > 0; i--)
    		finv[i] = finv[i + 1] * (i + 1) % p;
    }
    //组合数函数C(n,m)取模p
    ll C(ll n, ll m, ll p)
    {
    	if (n < m)
    		return 0;
    	return fac[n] * finv[m] % p * finv[n-m] % p;
    }
    

    当然实际使用时,不要忘记把初始化函数在主函数里调用。


    还有一个Lucas法以后用上了再更…

    展开全文
  • 利用费马小定理求逆元经典案例

    千次阅读 2018-07-24 22:35:08
    逆元的概念在这就不多说了 不知道的自行百度。 费马小定理:a是不能被质数p整除的正整数...利用费马小定理求逆元的前提强调p一定是质数。 说这些你可能不太明白,先看一道题就明白了, hdu1576题目:http://acm....

    逆元的概念在这就不多说了 不知道的自行百度。

    费马小定理:a是不能被质数p整除的正整数,则有a p−1 ≡ 1 (mod p)

    推导:a^(p−1) ≡ 1 (mod p) = a*a^(p−2 )≡ 1 (mod p) ;

    则a的逆元 为 a^(p−2)。利用费马小定理求逆元的前提强调p一定是质数。

    说这些你可能不太明白,先看一道题就明白了,

    hdu1576题目:http://acm.hdu.edu.cn/showproblem.php?pid=1576

        要求(A/B)%9973,但由于A很大,我们只给出n(n=A%9973)(我们给定的A必能被B整除,且gcd(B,9973) = 1)。

    Input 
    数据的第一行是一个T,表示有T组数据。 
    每组数据有两个数n(0 <= n < 9973)和B(1 <= B <= 10^9)。

    Output 
    对应每组数据输出(A/B)%9973。

    Sample Input 

    1000 53 
    87 123456789

    Sample Output 
    7922 
    6060 

    如果我们直接求肯定不行 ,所以要利用逆元求解,并且9973(即是上面的p)为质数,

    设C是B的逆元,则有B*C≡1(mod P); 推论:(A/B)mod P = (A/B)*1mod p = (A/B)*B*C mod p=A*C(mod p); 即A/B的模等于A*(B的逆元)的模;l利用费马小定理得出C=B^(p-2);则原式可转化为(A*C)%p=(A%p*C%p)%p;个人见解,欢迎纠错

    代码:

    #include<stdio.h>
    #include<math.h>
    #define mod 9973
    typedef long long ll;//对 long long重命名 
    ll DD(ll a ,ll b)//求解 a^b%mod(因为a^b太大 需利用快速幂求解) 
    {
        ll res=1;
        if(b<0)
        return 0;
        while(b)
        {
            if(b&1) res=res*a%mod;
            a=a*a%mod;
            b>>=1;
        }
        return res;
    }
    int main()
    {
        
        ll a,b,i;
        ll t;
        scanf("%lld",&t);
        while(t--)
        {
            scanf("%lld %lld",&a,&b);
            i=DD(b,(mod-2));//i即为 b的逆元 
        printf("%lld\n",(a%mod*i%mod)%mod); //A*C)%p=(A%p*C%p)%p 
        }
        return 0;
    }

    展开全文
  • 快速幂——序列求和(费马小定理求逆元) 题目描述 定义S(n) = 12 + 22 + … + n2,输出S(n) % 1000000007。 注意:1 < n < 1e18。 输入描述 多组输入,输入直到遇到EOF为止; 第一行输入一个正整数n。 输出...
  • 51nod1119 机器人走方格 v2 费马小定理求逆元 题解:向右总共走n-1,向左总共走m-1,总步数就是n+m-1。所以答案就是C(n+m-1,n-1),n+m-2步中挑其中n-1步向右。本题数据较大,不可以通过单纯组合数的公式(杨辉三角...
  • /*步大步算法+费马小定理求逆元 如果p为素数,a为整数,则a^(p-1)=1(mod p) -> a^(p-2)=(a^(-1))(mod p) Baby-Steps-Giant-Steps算法 高次同余方程。 A^x== B (mod C) 这里用到baby_step,giant_step算法。意为先...
  • 费马小定理求逆元

    2019-01-13 20:29:21
    费马小定理(Fermat's little theorem)是数论中的一个重要定理,在1636年提出,其内容为: 假如p是质数,且gcd(a,p)=1,那么 a^(p-1)≡1(mod p),例如:假如a是整数,p是质数,则a,p显然互质(即两者只有一个公约数1...
  • 关于费马小定理:https://www.cnblogs.com/rstz/p/12359948.html 1 #include <iostream> 2 #define mod 1000000007 3 using namespace std; 4 5 long long ksm(long long a, long long n){ 6 l...
  • Lucas定理: Cmn=C⌊m%p⌋⌊n%p⌋∗Cm/pn/pCnm=C⌊n%p⌋⌊m%p⌋∗Cn/pm/pC_{n}^{m} = C_{\... 具体计算组合数时,由于涉及到除法取模,所以可以用费马小定理求逆元。 由于gcd(a,p)=1gcd(a,p)=1gcd(a, p) =...
  • }//此处为中国剩余定理里面的。   费马 long long mpow(int a,int b,int modd) { int rt = 1; for( ; b; b >>= 1, a = (1ll * a * a)% modd) { if(b&1) rt = (1ll * rt * a) % modd; } return rt; }...
  • 逆元 Inverse element 1.什么是逆元 当求解公式:(a/b)%m 时,因b可能会过大,会出现爆精度的情况,所以需变除法为乘法: 设c是b的逆元,则有b*c≡1(mod m);//(b*c-1)%9973=0 ,我们称 c 是 b 关于 m 的...
  • 而使用费马小定理的代码 # include # include # include # include using namespace std ; const int maxn = 1e5 + 5 ; const int mod = 9973 ; typedef long long ll ; ...
  • S(n,m - 1) = S(n,m) - C(n,m) S(n,m + 1) = S(n,m) + C(n,m + 1) S(n - 1,m) = (S(n,m) + C(n - 1,m))...推出四道公式,用莫队算法做,组合数用费马小定理求逆元。 #include&lt;bits/stdc++.h&gt; #...
  • 费马小定理 扩展欧几里得 用来求逆元 当(a/b)%mod 时不能直接不能对分子分母单独取模 必须先b的逆元再进行取模运算 x = a ^ ( p - 2 ) (mod p) (a*x)%mod x为的逆元 费马小定理  假如a是一个整...
  •        题目给定两种箱子,一种给你一定数量金币,一种吃掉你所有金币。然后你要安排箱子顺序,使得获得的金币期望最小。...除法取模就一波逆元相乘即可。    &nb
  • 数论--费马小定理求逆元

    千次阅读 2019-12-09 20:00:37
    int Fermat_inverse(int a,int mod) { int res = 1; for(int i = 1;i < mod - 1;++i) res *= a; return res;...//如果p为大素数,我们可以用快速幂求解,时间复杂度为: ...long long fast_pow_mod(long long a,long...
  • 来源:牛客网   时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 262144K,其他语言...Applese 和它的伙伴参加了一个促销的抽奖活动,活动的规则如下:有一个随机数生成器,能等概率生成 0∼99 之间的整数...
  • 1079 中国剩余定理 1.0 秒 131,072.0 KB 0 分 基础题 一个正整数K,给出K Mod 一些质数的结果,符合条件的最小的K。例如,K % 2 = 1, K % 3 = 2, K % 5 = 3。符合条件的最小的K = 23。 ...
  • 然后可以出b的逆元,将除法转换为乘法进行计算。b的逆元等于 b的(m-2)次方。 代码: #include<bits/stdc++.h> using namespace std; const int mod=9973; long long quickpow(long long t1,long lo...
  • 所以可用费马小定理求 b mod m 的逆元 c = b ^ (m-2) (mod m) (a / b) % m = (a * c) % m = ( (a % m) * (c % m) ) % m 题目给出 n = (a % m) 所以 (a / b) % m = ( n * (c % m) ) % m 这题因为...
  • ll power(int a, long long b)//a为要求的逆元,b为mod-2的值 { ll c = 1; for (; b; b >>= 1) { if (b & 1)c = (long long)c*a%mod; a = (long long)a*a%mod; } return c; }

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 5,767
精华内容 2,306
关键字:

费马小定理求逆元