#include <stdio.h>
#include <algorithm>
using namespace std;
typedef long long ll;
bool sw;
ll p[200], q[200];
ll d, e, pi, m;
void sub(ll a, ll b, ll c, int depth) {
if (c == 1) return;
else {
p[depth + 1] = 1;
q[depth + 1] = b / c;
sw = !sw;
sub(b, c, b%c, depth + 1);
p[depth] *= q[depth + 1];
p[depth] %= pi;
q[depth] *= q[depth + 1];
q[depth] += p[depth + 1];
q[depth] %= pi;
}
}
ll gcd(ll a, ll b) {
if (a % b == 0) return b;
else return gcd(b, a%b);
}
int main() {
int n;
ll tmp;
pi = 1000000007;
scanf("%d", &n);
while (n--) {
scanf("%lld %lld", &m, &e);
tmp = gcd(m, e);
m /= tmp;
e /= tmp;
if (m == 1) {
printf("%lld", e);
continue;
}
sw = true;
p[0] = 1;
q[0] = pi / m;
sub(pi, m, pi%m, 0);
d = q[0];
d *= (sw == true ? -1 : 1);
if (sw == true) d += pi;
printf("%lld\n", (d*e) % pi);
}
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
12 ms |
1084 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
