#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
#include <exception>
#include <stdexcept>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
using namespace std;

using ll = long long;

void encrypt(ll e, ll secret, ll N) {
    ll res = 1;
    while (e--) {
        res = res*secret%N;
    }
    cout << "Шифр: <" << res << ">\n";
}

void decrypt(ll d, ll open, ll N) {
    ll res = 1;
    while (d--) {
        res = res*open%N;
    }
    cout << "Ответ: <" << res << ">\n";
}

void find_d(ll e, ll phi) {
    cout << "e = " << e << ", φ = " << phi << "\n";
    while (e != 1) {
        ll ost = phi%e;
        ll c = phi/e;
        if (ost==1) {
            cout << "Начинай с " << ost << "=" << phi << "-" << e << "*" << c << "\n";
        }
        else {
            cout << "Заменяй " << ost << " на " << phi << "-" << e << "*" << c << "\n";
        };

        phi = ost;
        swap(phi, e);
    }
}

int main() {
    ll first;
    cout << "1=Расшифровать, 2=Зашифровать? >> ";
    cin >> first;
    ll N, e;
    cout << "N, e (через пробел)? >> ";
    cin >> N >> e;
    if (first == 1) {
        ll q, p = 1;
        while (true) {
            p += 1;
            if (N%p==0) {
                q = N/p;
                break;
            }
        }
        ll phi = (p-1)*(q-1);
        find_d(e, phi);
        ll d=0;
        while (e*d%phi != 1) {
            cout << "У тебя должно получиться 1=" << e << "*u+" << phi << "*v. Введи u? >> ";
            cin >> d;
        }
        cout << "Верно! 🍻";
        ll tests;
        cout << "Кол-во данных? >> ";
        cin >> tests;
        while (tests--) {
            ll open;
            cout << "Введи зашифрованные данные? >> ";
            cin >> open;
            decrypt(d, open, N);
            cout << "\n";
        }
    }
    else if (first == 2) {
        ll tests;
        cout << "Кол-во данных? >> ";
        cin >> tests;
        while (tests--) {
            ll secret;
            cout << "Введи данные которые нужно зашифровать ? >> ";
            cin >> secret;
            encrypt(e, secret, N);
            cout << "\n";
        }
    }
    else {
        cout << "Неверный ввод";
    }
}