#include <iostream>
#include <string>

using namespace std;

// 扩展欧几里得算法求逆元
int gcdExtended(int a, int b, int x[]) {
    if (a == 0) {
        x[0] = 0;
        x[1] = 1;
        return b;
    }
    int x1[2];  // 用于保存递归结果
    int gcd = gcdExtended(b % a, a, x1);
    x[0] = x1[1] - (b / a) * x1[0];
    x[1] = x1[0];
    return gcd;
}

// 求模逆元
int modInverse(int a, int m) {
    int x[2];
    int g = gcdExtended(a, m, x);
    if (g != 1) {
        // 如果 a 和 m 不互质，逆元不存在
        return -1;
    }
    else {
        return (x[0] % m + m) % m;
    }
}

// 仿射加密
string encrypt(string plaintext, int a, int b) {
    string ciphertext = "";
    for (char c : plaintext) {
        if (isalpha(c)) {
            // 将字母转换为 0-25 之间的数值
            char base = isupper(c) ? 'A' : 'a';
            int x = c - base;
            // 加密公式：E(x) = (a * x + b) % 26
            char enc_char = (a * x + b) % 26 + base;
            ciphertext += enc_char;
        } else {
            ciphertext += c; // 非字母字符保持不变
        }
    }
    return ciphertext;
}

// 仿射解密
string decrypt(string ciphertext, int a, int b) {
    string plaintext = "";
    int a_inv = modInverse(a, 26); // 计算 a 的模逆元
    if (a_inv == -1) {
        cout << "解密失败：a 和 26 不互质，无法求逆元。" << endl;
        return "";
    }
    for (char c : ciphertext) {
        if (isalpha(c)) {
            char base = isupper(c) ? 'A' : 'a';
            int y = c - base;
            // 解密公式：D(y) = (a_inv * (y - b)) % 26
            char dec_char = (a_inv * (y - b + 26)) % 26 + base;
            plaintext += dec_char;
        } else {
            plaintext += c; // 非字母字符保持不变
        }
    }
    return plaintext;
}

int main() {
    int a, b;
    string choice, text;
    
    // 输入密钥
    cout << "请输入仿射加密的密钥 (a, b)：" << endl;
    cin >> a >> b;

    // 输入选择加密或解密
    cout << "你想执行加密还是解密？(encrypt/decrypt): ";
    cin >> choice;

    // 根据用户选择，输入明文或密文
    if (choice == "encrypt") {
        cout << "请输入明文: ";
        cin.ignore();  // 清除缓冲区中的换行符
        getline(cin, text);
        string ciphertext = encrypt(text, a, b);
        cout << "加密后的密文: " << ciphertext << endl;
    } else if (choice == "decrypt") {
        cout << "请输入密文: ";
        cin.ignore();
        getline(cin, text);
        string plaintext = decrypt(text, a, b);
        if (!plaintext.empty()) {
            cout << "解密后的明文: " << plaintext << endl;
        }
    } else {
        cout << "无效的操作选项。" << endl;
    }

    return 0;
}