Submission #19471

#	Time	Username	Problem	Language	Result	Execution time	Memory
19471		nosiar	Σ (kriii4_P2)	C++14	0 / 100	14 ms	1876 KiB

P2

#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;
}

• Subtask 1: 0 / 100