牛客小白月赛9 A 乘法逆元

乘法逆元复习一哈

什么是逆元；为了解决a/b在计算机中无法取模的问题

就有（a*1/b）%mod  //不可行

于是在0~mod-1中找一个逆元x

（a/b) %mod=（a*x）%mod

化简得（b*x）%mod=1即bx≡1(mod mod)

怎么解这个方程？

费马小定理：假如a,p是互质(即gcd(ap)=1),且p是质数,那么a^(p-1)≡1(mod p)也就是说,如果n是质数bx=1(mod mod)就可以转化成b*b^(mod-2)=1(mod mod)也就是说x= b^(mod-2)(mod mod)

这题用的快速幂写法求逆元 

#include<iostream>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
ll npow(ll a,ll b){
    ll ans=1;
    while(b){
        if(b&1){
            ans=ans*a%mod;
        }
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}
int main(){
    ll n,a,b,sum=1ll;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a>>b;
        ll x=npow(b,mod-2);
//        cout<<x<<endl;
        ll k=a*x;
        while(k<0){
            k+=mod;
        }
        k%=mod;
        sum=sum*(1-k)%mod;//这里不能用sum*=因为最后再乘sum会爆long long 
    }
    ll k=1-sum;
    while(k<0){
        k+=mod;
    }
    cout<<k%mod<<endl;
}

最后

以上就是忧虑台灯为你收集整理的牛客小白月赛9 A 乘法逆元的全部内容，希望文章能够帮你解决牛客小白月赛9 A 乘法逆元所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。