問題描述

給定日期區間 [y1 m1 d1, y2 m2 d2]，計算區間內「月份是素數 且 日期是素數」的天數。年份 1000~2999，含閏年規則。

關鍵觀察

• 素數月份固定：{2,3,5,7,11}（5個月）。
• 素數日期固定：{2,3,5,7,11,13,17,19,23,29,31}（11天，視月份長度截取）。
• 平年每月天數固定，閏年 2 月 29 天。
• 完整年份內符合條件天數固定：平年 52 天，閏年 53 天（2月多一天，29是素數）。

算法流程

1. 預計算 is_prime[1..31]、month_days[12]、is_leap(y)。
2. 若同年：直接遍歷月份、日期判斷。
3. 跨年：分三段處理
   • 首年尾部：從 m1,d1 到 12 月底。
   • 中間完整年：逐年累加 52/53。
   • 末年頭部：從 1 月 1 日到 m2,d2。

代碼實現

#include <iostream>
using namespace std;

bool prime[32] = {0,0,1,1,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,1,0,1};
int mdays[13] = {0,31,28,31,30,31,30,31,31,30,31,30,31};

bool is_leap(int y) {
    return (y%4==0 && y%100!=0) || y%400==0;
}

int count_in_month(int y, int m, int d_start, int d_end) {
    if (!prime[m]) return 0;
    int lim = mdays[m];
    if (m==2 && is_leap(y)) lim = 29;
    d_end = min(d_end, lim);
    int cnt = 0;
    for (int d = d_start; d <= d_end; ++d)
        if (prime[d]) ++cnt;
    return cnt;
}

int main() {
    int T; cin >> T;
    while (T--) {
        int y1,m1,d1, y2,m2,d2;
        cin >> y1 >> m1 >> d1 >> y2 >> m2 >> d2;
        long long ans = 0;
        
        if (y1 == y2) {
            if (m1 == m2) ans = count_in_month(y1, m1, d1, d2);
            else {
                ans += count_in_month(y1, m1, d1, mdays[m1]);
                for (int m = m1+1; m < m2; ++m) ans += count_in_month(y1, m, 1, mdays[m]);
                ans += count_in_month(y1, m2, 1, d2);
            }
        } else {
            // 首年
            ans += count_in_month(y1, m1, d1, mdays[m1]);
            for (int m = m1+1; m <= 12; ++m) ans += count_in_month(y1, m, 1, mdays[m]);
            // 中間完整年
            for (int y = y1+1; y < y2; ++y) ans += is_leap(y) ? 53 : 52;
            // 末年
            for (int m = 1; m < m2; ++m) ans += count_in_month(y2, m, 1, mdays[m]);
            ans += count_in_month(y2, m2, 1, d2);
        }
        cout << ans << '\n';
    }
    return 0;
}

優化提示

• 中間完整年可用 400 年週期快速計算：400 年中閏年 97 個，平年 303 個，總天數 = 97×53 + 303×52 = 20800。但題目年份跨度 ≤ 2000，直接循環足夠快。
• count_in_month 可預計算每月素數日期前綴和，O(1) 查詢。

複雜度

• 時間：O(年份跨度) ≤ 2000，T ≤ 50，極快。
• 空間：O(1)。

總結

ZOJ 3326 是典型的「日期模擬 + 數論篩選」題。關鍵在於識別固定的素數月份/日期集合，利用完整年份固定計數避免逐日遍歷。代碼結構清晰分段處理同年/跨年、首尾年/中間年，邊界條件（閏年 2 月、月份天數）逐一處理，即可準確高效解決。