题意分析

1. 加密明文（$n$）至密文（$m$），$m = n \times a$。
2. 解密密文至明文（设解密出的为 $n'$），$n' = m \times b$。
3. 给定 $a$，求 $b$。

---

整理条件可以得出：

$$(n \times a) \times b \equiv n \pmod {100000}$$

或：

$$n \times (a \times b) \equiv n \pmod {100000}$$

继续推导得到：

$$a \times b \equiv 1 \pmod {100000}$$

---

问题转化：求 $a \mod 100000$ 下的乘法逆元。

思路

特判

推导：

$$a \times x \equiv 1 \pmod m \\ a \times x - 1 = k \times m \\ a \times x - (k \times m) = 1 \\ a \times x + m \times (-k) = 1 \\ $$

根据裴蜀定理：

对于任意整数 $a, b$，一定存在整数 $x, y$ 使得 $ax + by = \gcd(a, b)$。

继续推导式子，我们得到：

$$\gcd(a, 100000) = 1$$

本题中 $m = 100000 = 2^5 \times 5^5$，因此如果 $a$ 可以被 $2$ 或 $5$ 整除则 $\gcd(a, 100000) \neq 1$，无满足条件 $b$。

扩展欧几里得

扩展欧几里得用于在线性时间内求解裴蜀定理。

思想

$$\gcd(a, b) = \gcd(b, a \bmod b)$$

推导式子：

显然 $a \bmod b = a - \lfloor a \div b \rfloor \times b$。

设两个未知数 $x', y'$。

开始推导：

$$\gcd(a, b) = bx' + (a - \lfloor a \div b \rfloor \times b) \times y' \\ \gcd(a, b) = bx' + ay' - \lfloor a \div b \rfloor \times b \times y' \\ \gcd(a, b) = ay' + b(x' - \lfloor a \div b \rfloor \times b \times y') \\ $$

对比 $\gcd(a, b) = ax + by$，得出：

$x = y', y = x' - \lfloor a \div b \rfloor \times b \times y'$

递归模拟过程即可。

代码

#include <bits/stdc++.h>
using namespace std;

int exgcd(int a, int b, int &x, int &y)
{
    if (b == 0)
    {
        x = 1;
        y = 0;
        return a;
    }
    int gcd = exgcd(b, a % b, y, x);
    y -= (a / b) * x;
    return gcd;
}
int a;
const int MOD = 100000;

int main()
{
    cin >> a;

    int x, y;
    if (exgcd(a, MOD, x, y) != 1)
    {
        cout << "NO" << "\n";
        return 0;
    }
    int b = (x % MOD + MOD) % MOD;
    if(b < 100 || b > 9999)
        cout << "NO" << "\n";
    else
        cout << b << endl;
    return 0;
}