明明的幸運數：含3或3的倍數計數問題的數學解法與代碼實現

問題描述

統計 1 到 N (N≤32767) 中「幸運數」的個數。幸運數定義：能被 3 整除，或十進制表示中包含數字 3。

解題思路

直接遍歷 1 到 N，對每個數判斷：

1. 若 i % 3 == 0 → 計數器++
2. 否則檢查各位數字是否含 3：反復取模 10 和除 10

時間複雜度 O(N log N)，N≤32767 瞬間通過。

代碼實現

#include <stdio.h>

int contains_3(int num);

int main() {
    int i, count = 0, num;
    scanf("%d", &num);

    for (i = 1; i <= num; i++) {
        if (i % 3 == 0) count++;
        else if (contains_3(i)) count++;
    }

    printf("%d", count);
    return 0;
}

int contains_3(int num) {
    while (num) {
        if (num % 10 == 3) return 1;
        num /= 10;
    }
    return 0;
}

優化思路（大數擴展）

若 N 很大（如 10^9），可用數位 DP：計算不含 3 且非 3 倍數的數，用總數減去。狀態：位置、模 3 餘數、是否已含 3、是否受上界限制。

測試樣例

輸入： 10
輸出： 3

1-10 中：3, 6, 9 為幸運數（3 的倍數），13 超出範圍。