「BZOJ 2296」随机种子 - 数论基础

给定一个数 x 0 \leq x \leq 10 ^ 6 ),求一个数 n 满足:

  1. n 的十进制表示中包含 0 ~ 9 的所有数;
  2. n ~ {\rm mod} ~ x = 0
  3. 0 \leq n \leq 10 ^ {16}

链接

BZOJ 2296

题解

做这题需要有点数论基础,构造方法并不难,首先为了满足性质 1,我们可以令 n 的十进制表示中的前 10 位为 9876543210 ,这样我们只需要考虑后 6 位即可。

d = 9876543210 \times 10 ^ 6 ~ {\rm mod} ~ x ,想象我们通过若干次减法把 9876543210 减到了 d ,所以我们只要令 n = 9876543210 \times 10 ^ 6 + x - d 即可。

注意 0 的特判。

代码

#include <cstdio>

const int MAXT = 100;
const int MAXX = 1e6;

int main() {
    int t;
    scanf("%d", &t);

    long long base = 9876543210 * 1e6;
    for (int i = 0; i < t; i++) {
        int x;
        scanf("%d", &x);
        printf("%lld\n", x == 0 ? -1LL : base + (x - base % x));
    }

    return 0;
}