| # |
제출 시각 |
아이디 |
문제 |
언어 |
결과 |
실행 시간 |
메모리 |
| 19483 |
2016-02-24T13:51:17 Z |
nosiar |
Σ (kriii4_P2) |
C++14 |
|
18 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) + mod) % mod;
}
int main() {
cin >> m;
long long ans = 0;
for(int i = 0; i < m; ++i)
{
cin>>n>>s;
ans = (ans+(s*inverse(n)))%mod;
}
cout << ans << endl;
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
11 ms |
1716 KB |
Output is correct |
| 2 |
Correct |
12 ms |
1716 KB |
Output is correct |
| 3 |
Correct |
14 ms |
1716 KB |
Output is correct |
| 4 |
Correct |
17 ms |
1716 KB |
Output is correct |
| 5 |
Correct |
17 ms |
1716 KB |
Output is correct |
| 6 |
Correct |
15 ms |
1716 KB |
Output is correct |
| 7 |
Correct |
13 ms |
1716 KB |
Output is correct |
| 8 |
Correct |
18 ms |
1716 KB |
Output is correct |
| 9 |
Correct |
12 ms |
1716 KB |
Output is correct |
| 10 |
Correct |
18 ms |
1716 KB |
Output is correct |
| 11 |
Correct |
17 ms |
1716 KB |
Output is correct |
| 12 |
Correct |
16 ms |
1716 KB |
Output is correct |
| 13 |
Correct |
17 ms |
1716 KB |
Output is correct |
| 14 |
Correct |
18 ms |
1716 KB |
Output is correct |
| 15 |
Correct |
16 ms |
1716 KB |
Output is correct |
| 16 |
Correct |
16 ms |
1716 KB |
Output is correct |
| 17 |
Correct |
17 ms |
1716 KB |
Output is correct |
| 18 |
Correct |
17 ms |
1716 KB |
Output is correct |
| 19 |
Correct |
16 ms |
1716 KB |
Output is correct |
| 20 |
Correct |
18 ms |
1716 KB |
Output is correct |
