题解 P7960 【[NOIP2021] 报数】

· · 题解

这次 T1 算是比较常规。

禁止报的数的生成规则与 埃氏筛法 类似，考虑用筛法预处理可以报出的数字列表和不可报出的数字，从而 O(1) 回答每一组询问。

具体来说，我们从 1 开始逐一处理每个正整数。当我们处理到数字 x 时，如果数字 x 尚未被标记为不合法，就通过拆位判断它是否合法。如果是合法数字，则将其加入合法数字列表，否则将 x 的所有倍数（包括 x 本身）全部标记为不合法数字；如果数字 x 已经被标记为不合法，则因为数字 x 的所有倍数都已经在之前和数字 x 一同被标为不合法数字，不需要再执行额外操作。

小细节：虽然 x \leq 10^7，但是要输出的下一个合法数字可能大于 10^7，因此筛的范围要稍微大一些（事实上，大于 10^7 的第一个合法数字是 10^7+1）。

问题来了，这个做法的时间复杂度是多少呢？是 O(n \log \log n) 吗？并不是。可以证明，该做法的时间复杂度是 O(n \log n)。

// Problem: P7960 [NOIP2021] 报数
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P7960
// Memory Limit: 512 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <iostream>
using namespace std;
const int maxn = 10000000 + 1000;
int vis[maxn + 5], lis[maxn + 5], cnt;
bool check(int x) {
  while (x) {
    if (x % 10 == 7) return false;
    x /= 10;
  }
  return true;
}
void init() {
  for (int i = 1; i <= maxn; i++)
    if (vis[i] == 0) {
      if (check(i)) {
        vis[i] = ++cnt;
        lis[cnt] = i;
      } else
        for (int j = 1; i * j <= maxn; j++) vis[i * j] = -1;
    }
}
int main() {
  ios::sync_with_stdio(false);
  int T;
  cin >> T;
  init();
  while (T--) {
    int x;
    cin >> x;
    if (vis[x] == -1)
      cout << -1 << endl;
    else {
      cout << lis[vis[x] + 1] << endl;
    }
  }
  return 0;
}