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.