1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71
| #define REP(i, s, e) for (int i = s; i <= e; i++) #define DREP(i, s, e) for (int i = s; i >= e; i--) #define DEBUG fprintf(stderr, "Passing [%s] in Line %d\n", __FUNCTION__, __LINE__)
#define chkmax(a, b) a = max(a, b) #define chkmin(a, b) a = min(a, b)
#include <iostream> #include <cstdio> #define int __int128
using namespace std;
template <typename T> T read() { T ans = 0, p = 1; char c = getchar(); while (!isdigit(c)) { if (c == '-') p = -1; c = getchar(); } while (isdigit(c)) { ans = ans * 10 + c - 48; c = getchar(); } return ans * p; } void write(int x) { if (x < 0) {putchar('-');write(-x);return;} if (x / 10) write(x / 10); putchar(x % 10 + '0'); }
int n, a1, b1, a2, b2, x;
int exgcd(int a, int b, int &x, int &y) { if (!b) { x = 1; y = 0; return a; } int ans = exgcd(b, a % b, y, x); y -= a / b * x; return ans; }
signed main() { #ifdef CraZYali freopen("4777-new-new.in", "r", stdin); freopen("4777-new-new.out", "w", stdout); #endif int n = read<int>(), b1 = read<int>(), a1 = read<int>(), lcm; x = a1; while (--n) { b2 = read<int>();a2 = read<int>(); int k, temp, g(exgcd(b1, b2, k, temp)); k *= (a2 - a1) / g; lcm = b1 * b2 / g; x = a1 = (b1 * k + a1) % lcm; b1 = lcm; } write((x + lcm) % lcm); return 0; }
|