Advertisement
reeps

c1

May 19th, 2019
122
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.71 KB | None | 0 0
  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. long long gcdex(long long a, long long b, long long &x, long long &y) {
  6.     if (a == 0) {
  7.         x = 0;
  8.         y = 1;
  9.         return b;
  10.     }
  11.     long long x1, y1;
  12.     long long d = gcdex(b % a, a, x1, y1);
  13.     x = y1 - (b / a) * x1;
  14.     y = x1;
  15.     return d;
  16. }
  17.  
  18. long long inv(long long a, long long m) {
  19.     long long x, y;
  20.     long long g = gcdex(a, m, x, y);
  21.     if (g != 1) {
  22.         return 0;
  23.     }
  24.     x = (x % m + m) % m;
  25.     return x;
  26. }
  27.  
  28. long long m, n = 0, b[50], a[15], r[15][15], x[15], ans = 0;
  29.  
  30. long long p[15] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
  31.  
  32. bool checkNumber(long long num) {
  33.     for (long long i = 0; i < m - 1; i++) {
  34.         if (num % (i + 2) != b[i]) {
  35.             return false;
  36.         }
  37.     }
  38.     return true;
  39. }
  40.  
  41. int main() {
  42.     cin >> m;
  43.     for (long long i = 0; i < m - 1; i++) {
  44.         cin >> b[i];
  45.         for (long long j = n; j < 15; j++) {
  46.             if (p[j] == i + 2) {
  47.                 a[n] = b[i];
  48.                 n++;
  49.                 break;
  50.             }
  51.         }
  52.     }
  53.     for (long long i = 0; i < n - 1; i++) {
  54.         for (long long j = i + 1; j < n; j++) {
  55.             r[i][j] = inv(p[i], p[j]);
  56.         }
  57.     }
  58.     for (long long i = 0; i < n; ++i) {
  59.         x[i] = a[i];
  60.         for (long long j = 0; j < i; ++j) {
  61.             x[i] = r[j][i] * (x[i] - x[j]);
  62.  
  63.             x[i] = x[i] % p[i];
  64.             if (x[i] < 0) x[i] += p[i];
  65.         }
  66.     }
  67.     long long multipl = 1;
  68.     for (long long i = 0; i < n; i++) {
  69.         ans += x[i] * multipl;
  70.         multipl *= p[i];
  71.     }
  72.     while (!checkNumber(ans)) {
  73.         ans += multipl;
  74.     }
  75.     cout << ans;
  76.     return 0;
  77. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement