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

About Inverse-modulo(逆元)

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 isa ^ (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.

赏