Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- using namespace std;
- long long gcdex(long long a, long long b, long long &x, long long &y) {
- if (a == 0) {
- x = 0;
- y = 1;
- return b;
- }
- long long x1, y1;
- long long d = gcdex(b % a, a, x1, y1);
- x = y1 - (b / a) * x1;
- y = x1;
- return d;
- }
- long long inv(long long a, long long m) {
- long long x, y;
- long long g = gcdex(a, m, x, y);
- if (g != 1) {
- return 0;
- }
- x = (x % m + m) % m;
- return x;
- }
- long long m, n = 0, b[50], a[15], r[15][15], x[15], ans = 0;
- long long p[15] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
- bool checkNumber(long long num) {
- for (long long i = 0; i < m - 1; i++) {
- if (num % (i + 2) != b[i]) {
- return false;
- }
- }
- return true;
- }
- int main() {
- cin >> m;
- for (long long i = 0; i < m - 1; i++) {
- cin >> b[i];
- for (long long j = n; j < 15; j++) {
- if (p[j] == i + 2) {
- a[n] = b[i];
- n++;
- break;
- }
- }
- }
- for (long long i = 0; i < n - 1; i++) {
- for (long long j = i + 1; j < n; j++) {
- r[i][j] = inv(p[i], p[j]);
- }
- }
- for (long long i = 0; i < n; ++i) {
- x[i] = a[i];
- for (long long j = 0; j < i; ++j) {
- x[i] = r[j][i] * (x[i] - x[j]);
- x[i] = x[i] % p[i];
- if (x[i] < 0) x[i] += p[i];
- }
- }
- long long multipl = 1;
- for (long long i = 0; i < n; i++) {
- ans += x[i] * multipl;
- multipl *= p[i];
- }
- while (!checkNumber(ans)) {
- ans += multipl;
- }
- cout << ans;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement