제출 #19499

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
19499		shjgkwo	Σ (kriii4_P2)	C++98	0 / 100	0 ms	1084 KiB

P2

#include <stdio.h>
#include <algorithm>
using namespace std;
typedef long long int lli;
bool sw;
lli p[200], q[200];
lli d, e, pi;
long long m;
void sub(lli a, lli b, lli 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];
	}
}
long long gcd(long long a, long long b) {
	if (a % b == 0) return b;
	else return gcd(b, a % b);
}
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", (d*e) % pi);
	}
	return 0;
}

• Subtask 1: 0 / 100