답안 #19471

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
19471 2016-02-24T13:26:41 Z nosiar Σ (kriii4_P2) C++14
0 / 100
14 ms 1876 KB
#include <iostream>
#include <tuple>
using namespace std;
long long mod = 1000000007;
long long m;
long long n[10000];
long long s[10000];
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[i]>>s[i];
	long long a=0,b=1;
	for(int i = 0; i < m; ++i)
		b = (b*n[i])%mod;
	for(int i = 0; i < m; ++i)
		a = (a + ((s[i] * b % mod) * inverse(n[i]) %mod))%mod;
	cout << (a*inverse(b))%mod << endl;
	
	return 0;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 1876 KB Output is correct
2 Incorrect 14 ms 1876 KB Output isn't correct
3 Halted 0 ms 0 KB -