NYOJ 664 數字整除：大數取模與數學技巧

題目轉化

判斷大整數 N 是否能被 17 整除。輸入以字符串形式給出，長度可達 105 位。利用同餘性質：

(a - b) % c = (a % c - b % c) % c

解法邏輯

• 將數字拆分：末位 c，前綴 A。原數 N = 10*A + c。
• 題目實際判斷 (A - 5*c) % 17 == 0（由 10 ≡ -7 (mod 17) 推導）。
• 若長度 < 10，直接 sscanf 轉整數計算。
• 否則逐位計算 A % 17，再與 (5*c) % 17 比較。

核心代碼

char str[105];
int main() {
    while (scanf("%s", str), str[0] != '0') {
        int len = strlen(str);
        if (len == 1) { puts("0"); continue; }
        int c = str[len-1] - '0';
        str[len-1] = '\0';
        if (len < 10) {
            int a; sscanf(str, "%d", &a);
            a -= c * 5;
            puts(a % 17 ? "0" : "1");
            continue;
        }
        int a = 0;
        for (int i = 0; i < len-1; ++i)
            a = (a * 10 + str[i] - '0') % 17;
        c = c * 5 % 17;
        puts((a - c) % 17 ? "0" : "1");
    }
    return 0;
}

關鍵技巧

1. 大數取模：逐位迭代 rem = (rem*10 + digit) % mod，避免大整數庫。
2. 模運算性質：利用負數模等價轉化，簡化判斷條件。
3. 邊界處理：單獨處理長度 1 和短數字情況，提升效率。