签到（乘法逆元）

本文主要是介绍签到（乘法逆元），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

夭寿了多会儿的题我现在才想起补orz

链接：https://ac.nowcoder.com/acm/contest/275/A
来源：牛客网

题目描述
你在一栋楼房下面，楼房一共有n层，第i层每秒有pi的概率会扔下一个东西并砸到你
求第一秒内你被砸到的概率
输入描述:
第一行一个整数n
之后有n行，第i+1行有两个整数ai,bi，表示
输出描述:
设答案为，你只需要找到一个最小的非负整数T，使得
输出这个T就行了
示例1
输入

复制
2
1 2
1 2
输出

复制
750000006
说明

一共只有如下状态：

1. 第一层和第二层都扔了下来

2. 第一层扔了下来

3. 第二层扔了下来

4. 第一层和第二层都没有扔下来

以上四种都是等概率发生的

除了第四种情况外，都会被砸到

因此被砸到的概率是 3/4，这个值在模1e9+7意义下就是750000006
备注:
数据范围
0 ≤ n ≤ 105
1 ≤ ai ≤ bi ≤ 105

题意很简单orz虽然我概率菜的一比但也知道是一减不被砸中的概率相乘
重点就是对ai/bi的取模orz众所周知除法取模就是乘以乘法逆元，又因为费马小定理可知a*ap-2≡1（mod p）

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod=1e9+7;
int n;
ll a,b,res;
ll pow_mod(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(){while(cin>>n){res=1;while(n--){cin>>a>>b;res=res*a%mod*pow_mod(b,mod-2)%mod;}cout<<(res+mod)%mod<<endl;}return 0;
}

这篇关于签到（乘法逆元）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---