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;
}
|
