Submission #19500

# Submission time Handle Problem Language Result Execution time Memory
19500 2016-02-24T14:19:40 Z shjgkwo Σ (kriii4_P2) C++
0 / 100
0 ms 1084 KB
#include <stdio.h>
#include <algorithm>
using namespace std;
typedef long long ll;
bool sw;
ll p[200], q[200];
ll d, e, pi;
long long 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];
		q[depth] *= q[depth + 1];
		q[depth] += p[depth + 1];
	}
}
int main() {
	int n;
	pi = 1000000007;
	scanf("%d", &n);
	while (n--) {
		scanf("%lld %lld", &m, &e);
		if (e % m == 0) {
			printf("%lld", e / m);
			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;
}
# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 1084 KB Output isn't correct
2 Halted 0 ms 0 KB -