nowcoder-946-A 筱玛爱地理

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 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;
}


<center>About  Inverse-modulo(逆元)</center>
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](https://zh.wikipedia.org/zh-hans/%E8%B4%B9%E9%A9%AC%E5%B0%8F%E5%AE%9A%E7%90%86),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);
}


<font color="red">So (a/b)%p=a*inv(b)%p.