逆元（关于除法取模）

2019-04-13 17:04发布

站内文章 / 模拟电子
12360 0 1767
每次除法取余都得去找板子，为了实现除法取余，先初步了解了一下逆元这个东西 关于逆元，首先要提一下费马小定理的一些内容 费马小定理：假如p是质数，且gcd(a,p)=1，那么 a^(p-1)≡1（mod p）。即：假如a是整数，p是质数，且a,p互质(即两者只有一个公约数1)，那么a的(p-1)次方除以p的余数恒等于1。 逆元：对于a和p，若a*b%p≡1，则称b为a%p的逆元。 定义什么的都不是关键，我们的目的很简单，就是要实现关于除法的取余，通过这些定理，来实现我们的目标 除法的逆元，即求(a/b)%p的值 通常情况下，p均为质数，则公约数为1的情况基本都可以保证 由费马小定理得： b^(p-1)%p=1 则： b*b^(p-2)%p=1 两边同乘a/b，然后左右式交换得： a/b=a/b*b*b^(p-2)%p 化简得： a/b=a*b^(p-2)%p 此时的结果即为a/b的结果，取模得(a/b)%p; #include using namespace std; #define ll long long ll mod; //宏定义一个mod //快速幂优化 ll quick_pow(ll a,ll b) { ll ans=1; while(b){ if(b&1) ans=(ans*a)%mod; b>>=1; a=(a*a)%mod; } return ans; } //逆元函数 公式为 (a/b)%mod=(a*b^(mod-2))%mod ll inv(ll a,ll b) { return (a*quick_pow(b,mod-2))%mod; } /*** 注意事项：逆元函数的使用，a必须能整除b，并且mod为质数 **/ int main() { ll a,b; while(cin>>a>>b>>mod){ cout< 前两天一个组合数的取余不会，从网上粘的板子，学了逆元，那组合数取余练练手，整理了一个组合数取余的板子，关于组合数取余，还有一个东西叫做卢卡斯定理，有时间再去学习一下 一道组合数取余的网址https://www.nowcoder.com/acm/contest/203/H 下面是自己总结的组合数取余模板  #include using namespace std; #define ll long long //组合数取模模板(p较大时，如p=1e9+7) ll Pow(ll a,ll b,ll p) { ll ans=1; while(b){ if(b&1) ans=(ans*a)%p; a=(a*a)%p; b>>=1; } return ans; } ll C(ll n,ll m,ll p) { if(m==0) return 1; if(m>n-m) m=n-m; ll up=1,down=1; for(int i=1;i<=m;i++){ up=(up*(n-i+1))%p; down=(down*i)%p; } return up*Pow(down,p-2,p)%p; } /*** 目的：输出C(n,m)%mod的值 时间复杂度：O(m) **/ int main() { ll m,n,p=1e9+7; while(scanf("%lld%lld",&n,&m)!=EOF){ printf("%lld ",C(n,m,p)); } return 0; }  

热门文章