Luogu1574 超级数

Luogu1574 超级数

数论

---

似乎重题 bzoj1053 [HAOI2007]反素数ant ？然而跑不过此题

首先发现 \(10^{17}\) 以内的反素数数量很少，可以直接打表解决……

然而有更优美的解法

由于数量少，显然有很多反素数是被重复计算了的

考虑继承，从大往小跑，如果上一个答案小于当前询问，当前询问的答案即为上一个答案

这种方法跑的很快，因为最多只会算遍所有反素数

代码

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn = 1e5 + 10;

const int p[] = {0, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47};

int n, tid[maxn];

ll now, res, val, Q[maxn], ans[maxn];

void dfs(int pos, ll sum, ll tot, int lst) {

  for (ll i = 0, t = sum; i <= lst; i++, t *= p[pos]) {

    if (pos < 16) dfs(pos + 1, t, tot * (i + 1), i);

    if ((res >= t && val <= tot) || (res < t && val < tot)) {

      res = t, val = tot;

    }

    if (t * p[pos] > now) break;

  }

}

int main() {

  scanf("%d", &n);

  for (int i = 1; i <= n; i++) {

    scanf("%lld", Q + i), tid[i] = i;

  }

  sort(tid + 1, tid + n + 1, [](int x, int y) {

    return Q[x] > Q[y];

  });

  for (int i = 1; i <= n; i++) {

    if (i > 1 && ans[tid[i - 1]] < Q[tid[i]]) {

      ans[tid[i]] = ans[tid[i - 1]];

    } else {

      res = val = 1;

      now = Q[tid[i]];

      dfs(1, 1, 1, 1000);

      ans[tid[i]] = res;

    }

  }

  for (int i = 1; i <= n; i++) {

    printf("%lld\n", ans[i]);

  }

  return 0;

}