链接：https://ac.nowcoder.com/acm/contest/946/A 筱玛爱地理 题目描述
筱玛是一个热爱地理的好筱玛。最近，在《地理II》作业本上，筱玛学到了“贝塔指数”的概念：
在经济地理学中，交通的联结度表示交通网络的发达程度，通常用贝塔指数来计算与比较。若用VVV表示一个交通网络中结点的数量，用EEE表示边的数量，则贝塔指数的计算方式为：β=EV\beta=\frac{E}{V}β=VE。
“实践是检验真理的唯一标准”。作为一个热爱地理的好筱玛，她马上就把新学的知识应用到实践当中去。筱玛一口气出了nnn张交通网络规划图，其中第iii张交通网络GiG_iGi有ViV_iVi个结点和EiE_iEi条边。筱玛一眼就看出了哪张图好、哪张图坏。但是作为一个负责任的好筱玛，她必须带领同学们一起进步。因此，她需要你将所有的nnn张图按照贝塔指数排序，并求出它们各自的贝塔指数在模109+710^9+7109+7意义下的值。 输入描述:
第一行一个整数nnn，表示交通网络规划图的数量。
接下来nnn行，每行两个整数ViV_iVi和EiE_iEi，分别表示图GiG_iGi中的结点数量和边的数量。
输出描述:
输出共nnn行，每行一个数，表示贝塔指数第iii大的交通网络的贝塔指数在模109+710^9+7109+7意义下的值。 如果不能整除，输出分数取模后的结果。
示例1 输入 复制
1 1 3
输出 复制
3
说明
显然此时β=EV=3\beta=\frac{E}{V}=3β=VE=3。
备注:
对于100%的数据，保证1≤n≤2×1051\le n\le 2\times10^51≤n≤2×105，1≤Vi,Ei≤1091\le V_i,E_i\le10^91≤Vi,Ei≤109。 必备知识：
费马小定理: 若p是质数，且p与a互质，有等式: a^(p-1) %p == 1 % p
那么我们在这上面变一下型: 俩边同除a a^(p-2)%p == a^(-1)%p
那么我们再在俩边同乘b (b / a)%p == b*a^(p-2)%p
a^-1 mod p = a^p-2 mod p; （m/a) mod p = （( m mod p) * ( a^-1 mod p)) mod p 逆元概念引入 (a + b) % p = (a%p + b%p) %p （对） (a - b) % p = (a%p - b%p) %p （对） (a * b) % p = (a%p * b%p) %p （对） (a / b) % p = (a%p / b%p) %p （错）
#include<bits/stdc++.h> #define ll long long using namespace std; const ll mod = 1e9 + 7; const ll N = 2e5 + 10; struct node { ll x; double ra; bool operator <(const node &y) const { return ra > y.ra; } } a[N]; int pow_mod(int a,int n,int m) //幂取模,运用分治方法 { //a为底数，n为指数，m为取模数 if(n==0) return 1; int x=pow_mod(a,n/2,m); long long int ans=(long long int)x*x%m; if(n%2==1) ans=ans*a%m; return (int)ans; } ll ksm(ll a, ll b) { ll ans = 1, base = a; while(b) { if(b&1) ans = (ans * base) % mod; base = (base * base) % mod; b >>= 1; } return ans; } int main() { ll n; cin >> n; for(int i = 0; i < n; i++) { int x, y; cin >> y >> x; a[i].ra = ((x * 1.0) / y); if(x % y != 0) a[i].x = (x % mod * ksm(y, mod - 2)) % mod; else a[i].x = int(x / y); } sort(a, a + n); for(int i = 0; i < n; i++) cout << a[i].x << endl; return 0; }