ZOJ 1489 2^x mod n = 1：數論與模指數最小正解

問題描述

給定正整數 n，求最小正整數 x 使得 2^x ≡ 1 (mod n)。無解輸出 "2^? mod n = 1"。

數論分析

• n = 1：模 1 任何數 ≡ 0，無解。
• n 為偶數：2^x 為偶數，2^x ≡ 1 (mod n) ⇒ 2^x = k·n + 1。右邊為奇數（偶數×k+1），左邊為偶數，矛盾。無解。
• n 為奇數：gcd(2, n) = 1，由歐拉定理 2^φ(n) ≡ 1 (mod n)，解必存在。最小正解為**模 n 下 2 的階**，整除 φ(n)。

算法：直接模擬乘法

從 x=1 開始，維持 `cur = (cur * 2) % n`，直到 `cur == 1`。因 n < 2^31，`cur` 用 64 位或乘法取模防溢出。

代碼 (C)

#include 
int main() {
    int n;
    while (~scanf("%d", &n)) {
        if (n == 1 || (n & 1) == 0) {
            printf("2^? mod %d = 1\n", n);
            continue;
        }
        int cur = 1;
        for (int x = 1; ; ++x) {
            cur = (cur * 2) % n;
            if (cur == 1) {
                printf("2^%d mod %d = 1\n", x, n);
                break;
            }
        }
    }
    return 0;
}

複雜度

最壞情況 x ≤ φ(n) < n，n 最大多少？題目未給上限，但通常 n ≤ 10^4 或 10^5，直接模擬足夠快。若 n 很大可用 Baby-step Giant-step 優化，但此題直接模擬即可 AC。

總結

利用同餘基本性質判斷無解情況（n=1、n 偶數），奇數情況下直接模擬 2 的冪次模 n，找到首次為 1 的指數。簡單的數論知識大幅縮減搜索空間。