idempotents

#include <iostream>
#include <cmath>
#include <vector>
#include <stack>
typedef long long i64;
using namespace std;

bool diophant(i64 a, i64 b, i64 c, i64 &x, i64 &y);
vector < i64 > idempotents(i64 n);

int main(){
    i64 n;
    cout << "Input N: ";
    cin >> n;
    vector <i64> answer = idempotents(n);
    cout << "Count of idempotents = " << answer.size() << endl;
    cout << "Idempotents: ";
    for (auto i : answer) cout << i << " ";
}

vector < i64 > idempotents(i64 n){
//  Нахождение идемпотентов в кольце вычетов по модулю n
    i64 m = n; // Запоминаем наше n
//  Разбиваем n на взаимно простые множители и кидаем в вектор v. Считаем кол-во этих множителей
    vector < i64 > v;
    int c = 0;
    for (i64 i = 2; i <= n; ++i)
        if (n % i == 0)
        {
            c++;
            v.push_back(i);
            n /= i;
            while (n % i == 0)
            {
                n /= i;
                v.back() *= i;
            }
        }
    n = m; // Возвращаем n исходное значение
//  Двоичный перебор всех представлений n = a * b , где НОД(a,b) = 1;
    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);
        x *= a; // a*x - один идемпотент
        // Приводим х к нормальному виду: 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;
}

bool diophant(i64 a, i64 b, i64 c, i64 &x, i64 &y){
        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;
        }
}