Luogu1574 超級數

\(n\) 次詢問不超過 \(a_i\) 的最大反素數

\(n\leq10^5,\ a_i\leq10^{17}\)

數論

---

似乎重題 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; }

轉載于:https://www.cnblogs.com/Juanzhang/p/10691962.html

總結

以上是生活随笔為你收集整理的Luogu1574 超级数的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。