| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 19461 |
2016-02-24T13:01:10 Z |
nosiar |
Σ (kriii4_P2) |
C++14 |
|
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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
1716 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
