[信息与未来 2016] 幸运数字(Lucky Numbers) 题解

思路分析

枚举 $x \in [1, n]$：若 x % 4 == 0 || x % 7 == 0 直接计入；否则不断取最低两位十进制数字判断 x % 100 == 44 || x % 100 == 77 并令 x /= 10。时间复杂度 $O(n \log_{10} n)$。

参考代码

#include <iostream>
using namespace std;

bool has44or77(int x)
{
    while (x >= 10)
    {
        int t = x % 100;
        if (t == 44 || t == 77) return true;
        x /= 10;
    }
    return false;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    if (!(cin >> n)) return 0;
    int ans = 0;
    for (int i = 1; i <= n; ++i)
    {
        if (i % 4 == 0 || i % 7 == 0 || has44or77(i)) ++ans;
    }
    cout << ans << "\n";
    return 0;
}