HDOJ 1393 Weird Clock：模擬與數學規律解題

問題理解

時鐘刻度 0-59，僅有分針。投入標記 d (1≤d≤1000) 的硬幣，分針順時針移動 當前時間 × d 分鐘。給定初始時間 s (1≤s≤59) 和 d，求最少投幣次數使分針歸零，不可能輸出 "Impossible"。

關鍵洞察

第 k 次投幣後時間：t_k = t_{k-1} × (d+1) mod 60。實際上是求最小 k 使 s × (d+1)^k ≡ 0 (mod 60)。由於模數 60 較小，直接模擬最多 60 步即可判斷。

模擬演算法

while (sc.hasNext()) {
    int s = sc.nextInt(), d = sc.nextInt();
    if (s == 0 && d == 0) break;
    int t = s;
    for (int i = 1; i <= 60; i++) {
        t = (t + t * d) % 60;  // 等價於 t = t * (d+1) % 60
        if (t == 0) { System.out.println(i); break; }
        if (i == 60) System.out.println("Impossible");
    }
}

數學分析（可選）

令 g = gcd(s, 60)，則 s/g 與 60 互質。需 (d+1)^k ≡ 0 (mod 60/g)，即 d+1 必須包含 60/g 的所有質因子。若 gcd(d+1, 60/g) = 1 則不可能。但模擬法更簡單通用。

測試樣例

30 1：30 → 30×2=60≡0 → 1 步。
1 2：1 → 3 → 9 → 27 → 21 → 3... 循環不含 0 → Impossible。