calc_number

#include <iostream>
#include <cmath>
#include <vector>
#include <stack>
typedef long long i64; // В коде будет слишком много long long, поэтому разумнее определить его как i64
using namespace std;

//  Функция решения диофантового уравнения a*x + b*y = c:
bool diophant(i64 a, i64 b, i64 c, i64 &x, i64 &y);
//  Функция поиска идемпотентов в кольце вычетов по модулю n, где n = произведение всех элементов вектора v
vector < i64 > idempotents_from_vector(vector <i64> & v);
//  Функция восстановления искомого числа по k известным остаткам от его деления на k известных взаимно простых числа
i64 calc_number(vector<i64> &idempotents, vector<i64> &v_z, vector<i64> &v_ost);

int main(){
    cout << "Input count of pairs [base and ost]: ";
    i64 count;
    cin >> count;

    cout << "Input " << count << " pairs [base and ost]: " << endl;

//  Вектор v_z хранит все основания колец вычетов , введенные пользователем
//  Вектор v_ost хранит все остатки от сравнения по модулю с соответсвующим основанием кольца вычетов
//  В n записывается произведение всех элементов вектора v_z
    vector <i64> v_z, v_ost;
    i64 p, ost, n = 1;
    for (int i = 1; i <= count; ++i){
        cin >> p >> ost;
        v_z.push_back(p);
        v_ost.push_back(ost);
        n *= p;
    }

//  Вектор idempotents хранит все идемпотенты кольца вычетов с основанием n
    vector <i64> idempotents = idempotents_from_vector(v_z);

//  В переменной ans хранится результат выполнения функции calc_number - полученное нами число
    i64 ans = calc_number(idempotents, v_z, v_ost);

    cout << endl << "ANSWER: " << ans;

//  Раскоментировать этот участок кода, если необходимо выполнять ПРОВЕРКУ найденного числа согласно условию
//  cout << endl << endl << "CHECK THIS: " << endl;
//  for (int i = 0; i < count; ++i){
//      i64 a = v_z.at(i), b = v_ost.at(i);
//      cout << ans << " % " << a << " = " << b << " ";
//      if (ans % a == b) cout << "(true)"; else cout << "(false)";
//      cout << endl;
//  }

}

bool diophant(i64 a, i64 b, i64 c, i64 &x, i64 &y){
//  Решение диофантового уравнения a*x + b*y = c методом Евклида
    stack < i64 >q;
    i64 r;
    while (a % b != 0)
    {
        r = a % b;
        q.push(a / b);
        a = b;
        b = r;
    }
    if (b != 1)
    {
        return false;
    }
    else
    {
        i64 temp;
        x = 1;
        y = q.top();
        q.pop();
        while (!q.empty())
        {
            temp = x;
            x = -y;
            y = -temp - q.top() * y;
            q.pop();
        }
        x *= c;
        y *= -c;
        return true;
    }
}

vector < i64 > idempotents_from_vector(vector <i64> & v){
//  Нахождение идемпотентов в кольце вычетов по модулю n, где n - произведение всех элементов вектора v, состоящего из взаимно простых чисел
    i64 n = 1, m;
//  Вычисление n
    for (auto &i : v) n *= i;
//  Двоичный перебор всех представлений n = a * b , где НОД(a,b) = 1;
    int c = v.size();
    i64 limit = pow(2, c - 1), a, b, x, y;
    vector < i64 > answer; // Будет хранить найденные идемпотенты
//  Достаточно перебрать всего 2^(c-1) диофантовых уравнений, откуда мы вытащим один идемпотент
//  И для найденного идемпотента х посчитаем 1-х парный идемпотент
    for (i64 i = 1; i < limit; ++i)
    {
        m = i;
        a = b = 1;
        for (i64 j = 0; j < c; ++j)
        {
            if (m % 2 == 1)
                a *= v[j];
            else
                b *= v[j];
            m /= 2;
        }
        // Решаем полученное диофантово уравнение a*x + b*y = c
        diophant(a, b, 1, x, y);
        // a*x - один идемпотент
        x *= a;
        // Приводим х к нормальному виду: 0 <= x < n
        while (x < 0) x += n;
        while (x >= n) x -= n;
        // Находим парный к нему идемпотент
        y = n + 1 - x;
        // Кидаем оба идемпотента в вектор
        answer.push_back(x);
        answer.push_back(y);
    }
//  Ну и возвращаем вектор
    return answer;
}

i64 calc_number(vector<i64> &idempotents, vector<i64> &v_z, vector<i64> &v_ost){
//  Вектор idempotents хранит все идемпотенты кольца вычетов с основанием n
//  Вектор v_z хранит все основания колец вычетов , введенные пользователем
//  Вектор v_ost хранит все остатки от сравнения по модулю с соответсвующим основанием кольца вычетов
    i64 n = 1, num = 0;
//  Так как мы не передаём n , то посчитаем его как произведение всех элементов вектора v_z
    for (auto &i : v_z) n *= i;
//  Затем сопоставим каждому j-ому кольцу вычетов v_z[j] i-ый идемпотент кольца вычетов по модулю n
    for (auto &a : idempotents){
        int t = -1, k = 0;
        bool flag = true;
        for(auto &b : v_z){
            // Ищем единственную возможную единицу в остатке при делении a[i] на b[j] .
            // Все остальные остатки при делении a[i] на b[k], где k != j, должны быть нулями
            if (a % b == 1)
                if (t != -1){
                    flag = false;
                    break;
                } else
                    t = k;
            ++k;
        }
        // Если мы нашли соответсвующий идемпотент для v_z[t], то сразу умножаем его на v_ost[t] и прибавляем к искомому числу
        if ( flag ) {
            num += a*v_ost[t];
            if (num >= n) num %= n;
        }
    }
// Возвращаем искомое число
    return num;
}