牛客网 - [牛客练习赛49]筱玛爱地理(逆元)

链接：https://ac.nowcoder.com/acm/contest/946/A
来源：牛客网
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 524288K，其他语言1048576K
64bit IO Format: %lld

题目描述

筱玛是一个热爱地理的好筱玛。最近，在《地理II》作业本上，筱玛学到了“贝塔指数”的概念：

在经济地理学中，交通的联结度表示交通网络的发达程度，通常用贝塔指数来计算与比较。若用V表示一个交通网络中结点的数量，用E表示边的数量，则贝塔指数的计算方式为：β=EV。

“实践是检验真理的唯一标准”。作为一个热爱地理的好筱玛，她马上就把新学的知识应用到实践当中去。筱玛一口气出了n张交通网络规划图，其中第i张交通网络Gi有Vi个结点和Ei条边。筱玛一眼就看出了哪张图好、哪张图坏。但是作为一个负责任的好筱玛，她必须带领同学们一起进步。因此，她需要你将所有的n张图按照贝塔指数排序，并求出它们各自的贝塔指数在模10^9+7意义下的值。

输入描述

第一行一个整数n，表示交通网络规划图的数量。
接下来n行，每行两个整数Vi和Ei，分别表示图Gi中的结点数量和边的数量。

输出描述

输出共n行，每行一个数，表示贝塔指数第i大的交通网络的贝塔指数在模10^9+7意义下的值。
如果不能整除，输出分数取模后的结果。

输入

1
1 3

输出

3

说明

显然此时β=EV=3。

备注

对于100%的数据，保证1≤n≤2×10^5，1≤Vi,Ei≤10^9。

解题思路

将给定的n个数按照E[i]/V[i]排序，再求逆元即可，注意比较大小时用乘法，不要直接除避免精度误差。

Accepted Code:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 200010;
const int MOD = 1e9 + 7;
struct edge {
    int v, e;
    bool operator < (const edge &S) const {
        return 1ll * e * S.v > 1ll * S.e * v;
    }
}G[N];
ll POW(ll a, ll b = MOD - 2, ll c = MOD) {
    ll res = 1;
    ll base = a % c;
    while (b) {
        if (b & 1)
            res = (res * base) % c;
        base = (base * base) % c;
        b >>= 1;
    }
    return res;
}
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d%d", &G[i].v, &G[i].e);
    sort(G + 1, G + n + 1);
    for (int i = 1; i <= n; i++)
        cout << G[i].e * POW(G[i].v) % MOD << endl;
    return 0;
}