算法
(暴力,模拟) $O(\log n)$
从 $n$ 开始枚举所有大于等于 $n$ 的整数 $x$,判断 $x$ 是否是特殊数字。
时间复杂度
结论:被枚举到的整数不超过 $19$ 个(实际的上限应该更低)。
记 $t = 10 \lfloor \frac {n + 9} {10} \rfloor$(即不小于 $n$ 的最小的 $10$ 的倍数)。
将枚举的数分成两部分:
- 从 $n$ 到 $t - 1$
- 从 $t$ 到 $t + 3$
不管第一部分中是否存在特殊数字,第二部分中总存在特殊数字。
从 $n$ 到 $x - 1$ 被枚举的数不超过 $9$ 个,从 $x$ 到 $x + 3$ 被枚举的数不超过 $4$ 个,总共不超过 $13$ 个。
所以枚举的数不超过 $13$ 个。
每次求十进制各位之和复杂度是 $\log n$,所以时间复杂度为 $O(13 \log n) = O(\log n)$ 。
C++ 代码
#include <cstdio>
int n;
bool check(int x)
{
int res = 0;
while (x) res += x % 10, x /= 10;
return res % 4 == 0;
}
int main()
{
scanf("%d", &n);
while (!check(n)) ++n;
printf("%d\n", n);
return 0;
}
$$ $$