oj.uz

답안 #19461

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
19461 2016-02-24T13:01:10 Z nosiar Σ (kriii4_P2) C++14
0 / 100
 17 ms 1716 KB 
#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;
}

Subtask #1
0.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 17 ms 1716 KB Output isn't correct
2 Halted 0 ms 0 KB -