Submission #19509

#	Time	Username	Problem	Language	Result	Execution time	Memory
19509		shjgkwo	Σ (kriii4_P2)	C++98	100 / 100	16 ms	1084 KiB

P2

#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;
	ll ans = 0;
	scanf("%d", &n);
	while (n--) {
		scanf("%lld %lld", &m, &e);
		tmp = gcd(m, e);
		m /= tmp;
		e /= tmp;
		if (m == 1) {
			ans += e;
			ans %= pi;
			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;

		ans += d * e;
		ans %= pi;
	}
	printf("%lld", ans);
	return 0;
}

• Subtask 1: 100 / 100