HDU 5373 The shortest problem：模擬與數學（11 的倍數判定）

題目大意

給定整數 n，重複 t 次操作：計算 n 的各位數字和，將其拼接到 n 末尾形成新數。問最終數是否能被 11 整除。n ≤ 10^4, t ≤ 10^5。

關鍵觀察

一個數能被 11 整除，當且僅當其奇數位數字和與偶數位數字和之差能被 11 整除。無需構造巨大數字，只需維護奇、偶位和的差值。

算法流程

1. 將初始 n 拆解為數字陣列，計算初始奇偶位和 ji, ou。
2. 每次操作：計算當前數字和 sum，將 sum 的各位依次加入，交替更新 ji 和 ou。
3. 重複 t 次後，判斷 (ji - ou) % 11 == 0。

參考代碼 (C++)

#include <cstdio>
#include <cstring>
using namespace std;

void work(int n, long long &sum, int *a, int &len) {
    if (n == 0) { len = 1; a[0] = 0; return; }
    while (n) {
        int t = n % 10; n /= 10;
        sum += t; a[len++] = t;
    }
}

int main() {
    int n, t, T = 0;
    while (scanf("%d%d", &n, &t) != EOF) {
        if (n == -1 && t == -1) break;
        printf("Case #%d: ", ++T);
        long long ji = 0, ou = 0;
        int a[100005], len = 0;
        long long sum = 0;
        work(n, sum, a, len);
        int flag = 1;
        for (int i = len - 1; i >= 0; i--) {
            if (flag) ji += a[i]; else ou += a[i];
            flag ^= 1;
        }
        for (int i = 0; i < t; i++) {
            len = 0; sum = 0;
            work(sum, sum, a, len); // 計算 sum 的各位
            flag = 1;
            for (int j = len - 1; j >= 0; j--) {
                if (flag) ji += a[j]; else ou += a[j];
                flag ^= 1;
            }
        }
        if ((ji - ou) % 11 == 0) printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}