题解：P13185 [GCJ 2016 Qualification] Counting Sheep

· · 题解

正解（附证明）

当 N = 0 时，容易发现无法达成目标。

当 N > 0 时，结论：一定可以达成目标。

考虑证明：首先，每连续 N 个正整数中，必有一个为 N 的倍数。

我们尝试构造，设 N 位数为 k，记 123456789 \times 10^{k+1} 为 a，则有上面定理知 a+1 到 a+N 中必有一个为 N 的倍数，且 0 到 9 在前面都存在，满足条件。

于是简单模拟即可，用 flag_i 记录 i 这个阿拉伯数字是否出现过，全部出现过即找到答案，输出即可。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int T, N;
bool flag[10];
int main(void) {
    cin.tie(0), cout.tie(0);
    cin >> T;
    for (int t = 1; t <= T; ++t) {
        cin >> N;
        if (!N) {
            cout << "Case #" << t << ": INSOMNIA\n";
            continue;
        }
        memset(flag, false, sizeof flag);
        int num = 0, now = 0, tmp = 0;
        while (num < 10) {
            now += N;
            tmp = now;
            while (tmp) {
                int tot = tmp % 10;
                if (!flag[tot]) {
                    flag[tot] = true;
                    ++num;
                    if (num == 10) break;
                }
                tmp /= 10;
            }
        }
        cout << "Case #" << t << ": " << now << '\n';
    }
    return 0;
}

谢谢大家！（点个赞吧