Submission #19483

#	Time	Username	Problem	Language	Result	Execution time	Memory
19483		nosiar	Σ (kriii4_P2)	C++14	100 / 100	18 ms	1716 KiB

P2

#include <iostream>
#include <tuple>
using namespace std;
long long mod = 1000000007;
long long m,n,s;
tuple<long long, long long, long long> extended_gcd(long long a, long long b)
{
    if (b == 0)
        return tuple<long long, long long, long long> { a, 1, 0 };
 
    auto r = extended_gcd(b, a % b);
 
    long long d = get<0>(r);
    long long x = get<1>(r);
    long long y = get<2>(r);
 
    return tuple<long long, long long, long long>{ d, y, x - a/b*y };
}
 
/* a has a (unique) multiplicative inverse iif gcd(a,n)=1 */
long long inverse(long long a)
{
    auto r = extended_gcd(a, mod);
    if (get<0>(r) != 1) return -1;
    return (get<1>(r) + mod) % mod;
}
int main() {
    cin >> m;
    long long ans = 0;
    for(int i = 0; i < m; ++i)
    {
        cin>>n>>s;
        ans = (ans+(s*inverse(n)))%mod;
    }
    cout << ans << endl;
     
    return 0;
}

• Subtask 1: 100 / 100