「POJ-2891」Strange Way to Express Integers-扩展欧几里德

Elina is reading a book written by Rujia Liu, which introduces a strange way to express non-negative integers. The way is described as following:
Choose k different positive integers a1, a2, \cdots , ak. For some non-negative m, divide it by every ai (1 \leq i \leq k) to find the remainder ri. If a1, a2, \cdots , ak are properly chosen, m can be determined, then the pairs (ai, ri) can be used to express m.

“It is easy to calculate the pairs from m, ” said Elina. “But how can I find m from the pairs?”

Since Elina is new to programming, this problem is too difficult for her. Can you help her?

链接

POJ-2891

代码

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
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cctype>
#include <iostream>
typedef long long ll;
inline void exgcd(ll a, ll b, ll &g, ll &x, ll &y) {
if (!b) x = 1, y = 0, g = a;
else exgcd(b, a % b, g, y, x), y -= (a / b) * x;
}
int main() {
std::ios::sync_with_stdio(0), std::cin.tie(0);
register int n;
register ll a, b, c1, c2, c, x, y, d;
while (std::cin >> n) {
std::cin >> a >> c1;
register int f = 1;
for (register int i = 1; i < n; i++) {
std::cin >> b >> c2, exgcd(a, b, d, x, y), c = c2 - c1;
if (c % d) f = 0;
c /= d;
ll t = b / d;
x = (x * c % t + t) % t, c1 += a * x, a = a / d * b, c1 %= a;
}
if (f) std::cout << c1 << "\n";
else std::cout << "-1\n";
}
return 0;
}
#

Comments

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×