Link: nowcoder-946-A
Description:
筱玛是一个热爱地理的好筱玛。最近,在《地理II》作业本上,筱玛学到了“贝塔指数”的概念:
在经济地理学中,交通的联结度表示交通网络的发达程度,通常用贝塔指数来计算与比较。若用
V表示一个交通网络中结点的数量,用
E表示边的数量,则贝塔指数的计算方式为:β=E/V。
“实践是检验真理的唯一标准”。作为一个热爱地理的好筱玛,她马上就把新学的知识应用到实践当中去。筱玛一口气出了n张交通网络规划图,其中第i张交通网络Gi有Vi个结点和Ei条边。筱玛一眼就看出了哪张图好、哪张图坏。但是作为一个负责任的好筱玛,她必须带领同学们一起进步。因此,她需要你将所有的n张图按照贝塔指数排序,并求出它们各自的贝塔指数在模1e9+7意义下的值。
输入描述:
第一行一个整数n,表示交通网络规划图的数量。
接下来n行,每行两个整数Vi和Ei,分别表示图Gi中的结点数量和边的数量。
输出描述:
输出共n行,每行一个数,表示贝塔指数第i大的交通网络的贝塔指数在模1e9+7意义下的值。
如果不能整除,输出分数取模后的结果。
示例1
输入
1
1 3
输出
3
说明
显然此时
β=E/V=3。
备注:
对于100%的数据,保证
1≤n≤2×1e5,
1≤Vi,Ei≤1e9。
Problem solving:
Obviously,we can solve this problem through sort.But there has a unusual situation is fractional modulo.So we use Inverse-modulo(逆元) here.
Click to see Chinese Intentional analysis
显然是一个sort就可以解决的问题,但是更难得在于要对分数取模,这个时候就会用到逆元。Code:
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 1e9 + 7; struct node { ll x, y; double z; } a[200005]; bool cmp(node x, node y) { return x.z < y.z; } const int mod = 1e9 + 7; long long quickpow(long long a, long long b) { if (b < 0) return 0; long long ret = 1; a %= mod; while (b) { if (b & 1) ret = (ret * a) % mod; b >>= 1; a = (a * a) % mod; } return ret; } long long inv(long long a) { return quickpow(a, mod - 2); } int main() { ll n; cin >> n; for (ll i = 0; i < n; i++) { cin >> a[i].x >> a[i].y; a[i].z = a[i].y * 1.0 / a[i].x; } sort(a, a + n, cmp); for (ll i = n - 1; i >= 0; i--) cout <<a[i].y * inv(a[i].x) % maxn << endl; }
There are many ways to find it.But I love this way,it's easy to understand and remember.That is Fermat's little theorem,we can ues this when the mode is a prime number.
The Inverse-modulo(逆元) of a in mode p is
a ^ (p-2)
.Code:
const int mod = 1e9 + 7; long long quickpow(long long a, long long b) { if (b < 0) return 0; long long ret = 1; a %= mod; while (b) { if (b & 1) ret = (ret * a) % mod; b >>= 1; a = (a * a) % mod; } return ret; } long long inv(long long a) { return quickpow(a, mod - 2); }
So (a/b)%p=a*inv(b)%p.