| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 19471 |
2016-02-24T13:26:41 Z |
nosiar |
Σ (kriii4_P2) |
C++14 |
|
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;
}
| # |
Verdict |
Execution time |
Memory |
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 |
- |
