제출 #19461

#제출 시각아이디문제언어결과실행 시간메모리
19461nosiarΣ (kriii4_P2)C++14
0 / 100
17 ms1716 KiB
#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);
}
int main() {
	cin >> m;
	long long ans = 0;
	for(int i = 0; i < m; ++i)
	{
		cin>>n>>s;
		int inv_n = inverse(n);
		ans = (ans+(s*inv_n))%mod;
	}
	cout << ans << endl;
	
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...