素数

如果 $p$ 是奇素数，则 $x^2 \equiv 1 \pmod p$ 的解为 $x \equiv 1 \pmod p$ 或者 $x \equiv p - 1 \pmod p$．

容易验证，$p$ 为奇素数时，$x\equiv 1\pmod p$ 和 $x\equiv p-1\pmod p$ 都可以使得上式成立．由 Lagrange 定理 可知，这就是该方程的所有解．

设 $n-1=u2^t$，其中，$u$ 是奇数且 $t$ 是正整数．那么，整数 $n$ 可以通过基底为 $a$ 的 Miller–Rabin 素性测试说明

记这样的 $a$（的同余类）集合为 $S$，要说明的是

其中，$\varphi(n)$ 是 欧拉函数．证明分为三步．

第一步：设 $\ell$ 是使得 $2^\ell \mid p-1$ 对所有 $n$ 的素因子 $p$ 都成立的最大正整数．那么，可以证明

集合 $S$ 中的元素 $a$ 只有两种可能．如果 $a^u\equiv 1\pmod n$，那么，显然 $a^{u2^{\ell-1}}\equiv 1\pmod n$ 也成立，亦即 $a\in S'$．如果对于 $0\le i < t$ 成立 $a^{u2^i}\equiv -1\pmod n$，那么，对于任意素因子 $p\mid n$，都有 $a^{u2^i}\equiv-1\pmod p$．设 $\delta_p(a)$ 是 $a$ 模 $p$ 的 阶，那么，显然有 $\delta_p(a)\mid u2^{i+1}$ 但是 $\delta_p(a)\nmid u2^{i}$，这说明，$\delta_p(a)$ 的素因数分解中，$2$ 的指数恰为 $i+1$，因而 $2^{i+1}\mid\delta_p(a)$．由费马小定理可知，$\delta_p(a)\mid p-1$，所以，$2^{i+1}\mid p-1$．这一点对于 $n$ 的所有素因子 $p$ 都成立．因此，$i+1\le\ell$．这说明 $a^{u2^{\ell-1}} = (a^{u2^i})^{2^{\ell-1-i}} \equiv \pm 1 \pmod n$，同样有 $a\in S'$．综合两种可能，就得到 $S\subseteq S'$．

第二步：计算 $|S'|$ 的大小．

假设 $n$ 有素因数分解 $n = p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}$，那么，由 中国剩余定理 可知，条件 $a^{u2^{\ell - 1}}\equiv 1\pmod n$ 等价于 $a^{u2^{\ell - 1}}\equiv 1\pmod{p_i^{e_i}}$ 对所有 $p_i^{e_i}$ 都成立．由于模奇素数幂 $p_i^{e_i}$ 的 原根 总是存在的，所以，同余方程 $a^{u2^{\ell - 1}}\equiv 1\pmod{p_i^{e_i}}$ 的 解的数量 为

第一个等号成立，是因为 $u$ 是 $n-1$ 的因子，不可能是 $p_i$ 的倍数；第二个等号成立，是因为 $\ell$ 的选取方式．所以，由中国剩余定理可知，同余方程 $a^{u2^{\ell-1}}\equiv 1\pmod n$ 的解的数量为

同理，条件 $a^{u2^{\ell - 1}}\equiv -1\pmod n$ 等价于 $a^{u2^{\ell - 1}}\equiv -1\pmod{p_i^{e_i}}$ 对所有 $p_i^{e_i}$ 都成立．对于任意因子 $p_i^{e_i}$，条件 $a^{u2^{\ell - 1}}\equiv -1\pmod{p_i^{e_i}}$ 都等价于 $a^{u2^{\ell - 1}}\not\equiv 1\pmod{p_i^{e_i}}$ 且 $a^{u2^{\ell}}\equiv 1\pmod{p_i^{e_i}}$ 成立．类似上文，可以计算出同余方程 $a^{u2^{\ell}}\equiv 1\pmod{p_i^{e_i}}$ 的解的数量为 $2^{\ell}\gcd(u,p_i-1)$，因此，同余方程 $a^{u2^{\ell - 1}}\equiv -1\pmod{p_i^{e_i}}$ 的解的数量也等于

再次应用中国剩余定理，就得到同余方程 $a^{u2^{\ell - 1}}\equiv -1\pmod n$ 的解的数量等于

因此，综合两种情形，有

第三步：证明 $|S'|\le\varphi(n)/4$．

结合欧拉函数的表达式 $\varphi(n)=\prod_ip_i^{e_i-1}(p_i-1)$ 可知

对于每一个 $i$，相应的因子 $p_i^{e_i-1}\dfrac{p_i-1}{2^{\ell-1}\gcd(u,p_i-1)}$ 都是一个偶数，所以，$\varphi(n)/|S'|$ 是一个整数．假设 $|S'|\le\varphi(n)/4$ 不成立．必然有 $\varphi(n)/|S'|=1,2,3$，亦即

由于连乘式中的每个因子都是偶数，所以，这个连乘式要么只有一个因子且这个因子就等于 $2,4,6$，要么就只有两个因子且都等于 $2$．

首先考虑有两个因子的情形．此时，两个因子都没有奇素因子，所以，$p_i^{e_i-1}=1$，亦即 $n$ 没有平方因子．不妨设 $n=p_1p_2$ 且 $p_1<p_2$ 都是素数．两个因子都等于 $2$，所以，总有 $p_i-1=2^{\ell}\gcd(u,p_i-1)$．因此，$p_i=1+2^\ell m_i$，其中，$m_i$ 是奇数，而且 $m_i\mid u$．将 $p_1p_2=n=1+u2^t$ 对 $m_1$ 取模就得到 $p_1p_2\equiv 1\pmod{m_1}$，故而 $p_2\equiv 1\pmod{m_1}$，这说明，$m_1\mid m_2$．反过来也成立．这就说明 $m_1=m_2$，也就是 $p_1=p_2$．这与 $p_1<p_2$ 矛盾．这一情形不成立．

最后，考虑只有一个因子的情形，亦即合数 $n=p^e$ 且 $e>1$．此时，必然有 $p^{e-1}\mid 2,4,6$．因此，唯一的情形是 $p=3,e=2$，亦即 $n=9$，与命题所设相矛盾．这一情形也不成立．

综合所有情形可知，$|S'|\le\varphi(n)/4$ 成立．

结合上述三个步骤可知，$|S|\le |S'|\le \varphi(n)/4$ 对于所有奇合数 $n>9$ 都成立．

对于这种题，我们只要以因子数为 dfs 的返回条件基准，不断更新找到的最小值就可以了．

#include <iostream>
constexpr int p[15] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47};
// p 中的素数乘积超过了 1e18

int n;
long long ans = 2e18;

// u: 当前考虑的质数在 p 中的下标
// num: 当前构成的数值
// cnt: 当前数值的因数个数
// pre: 上一个因子的幂次，限定本次选择的幂次
void dfs(int u, long long num, long long cnt, int pre) {
  if (cnt > n || u >= 15) return;
  if (cnt == n) return ans = std::min(ans, num), void();
  for (int i = 1; i <= pre; ++i) {
    if (num * p[u] > ans) break;  // 剪枝
    dfs(u + 1, num *= p[u], cnt * (i + 1), i);
  }
}

int main() {
  std::cin >> n;
  dfs(0, 1, 1, 59);  // floor(log2(1e18))=19
  std::cout << ans << std::endl;
  return 0;
}

思路同上，只不过要改改 dfs 的返回条件．注意这样的题目的数据范围，32 位整数可能溢出．

#include <iostream>

int p[16] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53};
unsigned long long n;
unsigned long long ans,
    ans_num;  // ans 为 n 以内的最大反素数（会持续更新），ans_sum 为
              // ans的因子数。

// depth: 当前在枚举第几个素数
// temp: 当前因子数量为 num 的时候的数值
// num: 当前因子数
// up：上一个素数的幂，限制当前因子幂次上界
void dfs(int depth, unsigned long long temp, unsigned long long num, int up) {
  if (depth >= 16 || temp > n) return;
  if (num > ans_num) {  // 更新答案
    ans = temp;
    ans_num = num;
  }
  if (num == ans_num && ans > temp) ans = temp;  // 更新答案
  for (int i = 1; i <= up; i++) {
    if (temp * p[depth] > n)
      break;  // 剪枝：如果加一个这个乘数的结果比ans要大，则必不是最佳方案
    dfs(depth + 1, temp *= p[depth], num * (i + 1),
        i);  // 取一个该乘数，进行对下一个乘数的搜索
  }
  return;
}

using std::cin;
using std::cout;

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  while (cin >> n) {
    ans_num = 0;
    dfs(0, 1, 1, 60);
    cout << ans << '\n';
  }
  return 0;
}