UVA 10127 Ones：模運算構造最小全 1 倍數—— 數論經典入門

題目大意

給定整數 n (1 ≤ n ≤ 10000)，求最小的正整數 k，使得由 k 個 1 組成的數字（即 111...1，共 k 位）能被 n 整除。輸出 k。

核心數學洞察

設 R(k) = (10^k - 1) / 9 為 k 個 1 組成的數。
遞推關係：
R(1) = 1
R(k) = R(k-1) * 10 + 1

僅關心模 n 餘數：
rem(1) = 1 % n
rem(k) = (rem(k-1) * 10 + 1) % n

當 rem(k) == 0 時，R(k) 能被 n 整除，k 即為答案。

為什麼一定有解？

• 餘數空間 {0, 1, ..., n-1} 只有 n 種可能。
• 由鴿巢原理，最多 n+1 步必出現重複餘數。
• 若 0 未出現，序列進入循環，但 R(k) 嚴格遞增，不可能循環 → 矛盾。
  ∴ 0 必出現，解存在且 k ≤ n。

極簡代碼

#include <cstdio>

int main() {
    int n;
    while (~scanf("%d", &n)) {
        int rem = 1 % n, k = 1;
        while (rem != 0) {
            rem = (rem * 10 + 1) % n;
            ++k;
        }
        printf("%d\n", k);
    }
    return 0;
}

複雜度分析

• 時間：O(k)，最壞 O(n)，n ≤ 10000 瞬間通過。
• 空間：O(1)，僅需兩個整數變量。

測試樣例

易錯點提醒

1. n=1：rem = 1%1 = 0，循環不進入，直接輸出 k=1，正確。
2. 大數誤區：不要嘗試構造完整的 111...1 大整數，n=9999 時 k 可達數千位，超出任意基本類型。只做模運算。
3. 輸入結束：while (~scanf(...)) 處理 EOF，UVA 標準輸入格式。

延伸：同餘方程視角

求解 10^k ≡ 1 (mod 9n) 且 gcd(10, 9n)=1。
此即 乘法階 問題，k 為 10 模 9n 的階。本題遞推法本質上是暴力求階，因 n 小足夠高效。