HDU 4028 - The time of a day：LCM 性質 + STL 模擬預計算

問題

一天有 n 小時，每小時 m 分鐘，每分鐘 s 秒（n,m,s ≤ 40）。求一天中恰好有 k 種不同時刻的時間點數。多組查詢。

數學轉化

時刻 (h, min, sec) 對應總秒數 T = h*m*s + min*s + sec。一天總秒數 D = n*m*s。
不同時刻數 = D / gcd(T, D) 的因數個數？實際為：T 與 D 的最小公倍數相關。
經推導：不同時刻數 = LCM(T, D) / T = D / gcd(T, D)。但題目要求「恰好 k 種不同時刻」，即 D / gcd(T, D) = k。

預計算所有可能 T

• D ≤ 40³ = 64000，枚舉所有 T ∈ [0, D-1]
• 對每個 T 計算 k = D / gcd(T, D)
• 統計每個 k 出現的次數，建立前綴和
• 查詢 O(1) 回答

代碼骨架

map mp[41];
set myset[41];  // Node{num, ans} 按 num 排序
for (int i=1; i<=40; ++i) {
    mp[i] = mp[i-1];
    for (auto& p : mp[i-1]) {
        long long l = lcm(p.first, i);
        mp[i][l] += p.second;
    }
    mp[i][i]++;  // 新增單獨 i
    // 建立有序統計結構...
}

複雜度

• 預計算 O(40 × 狀態數)，狀態數極小（LCM 快速增長）
• 查詢 O(log 狀態數)