D - AABCC[数学] [时间复杂度分析]
D - AABCC (atcoder.jp)
问题陈述
有多少个不大于 $N$ 的正整数可以用三个素数 $a,b$ 和 $c$ 来表示 $a^2 \times b \times c^2$ ,使得 $a<b<c$ ?
- $N$是一个整数,满足 $300 \le N \le 10^{12}$。
这道题可以作为一道时间复杂度分析的例题
因为$a^2 \times b \times c^2 \le n$
所以$a^2 \times b \times c^2 \le 10^{12}$
因为$a<b<c$ ,又因为$a,b$ 和 $c$ 为素数
所以$3\le b ,2\le a $
所以$12 \times c^2 \le a^2 \times b \times c^2 \le 10^{12}$
所以$12 \times c^2 \le 10^{12}$
所以$c^2 \le \frac{10^{12}}{12}$
所以$c\le \sqrt{\frac{10^{12}}{12}}$
所以$c\le 288,676$
设$Π(x)$为素数函数
筛一下可以发现$Π(c)\le 25112$
然后直接暴力$for$遍历$i,j,k$
由于每一个$for$对于其素数都有单调性
然后总共的三层$for$的计算次数是答案的统计次数加上$break$的次数
可以近似的认为遍历次数就是答案数
因为样例给了
1000000000000
2817785
那么就可以在$2.8\times10^6$的时间复杂度内解决掉这道问题
code
#pragma GCC optimize( \
"-fdelete-null-pointer-checks,inline-functions-called-once,-fexpensive-optimizations,-foptimize-sibling-calls,-ftree-switch-conversion,-finline-small-functions,inline-small-functions,-frerun-cse-after-loop,-fhoist-adjacent-loads,-findirect-inlining,-freorder-functions,no-stack-protector,-fpartial-inlining,-fsched-interblock,-fcse-follow-jumps,-falign-functions,-fstrict-aliasing,-fschedule-insns2,-ftree-tail-merge,inline-functions,-fschedule-insns,-freorder-blocks,-funroll-loops,-fthread-jumps,-fcrossjumping,-fcaller-saves,-fdevirtualize,-falign-labels,-falign-loops,-falign-jumps,unroll-loops,-fsched-spec,-ffast-math,Ofast,inline,-fgcse,-fgcse-lm,-fipa-sra,-ftree-pre,-ftree-vrp,-fpeephole2", \
3, 2)
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include <bits/stdc++.h>
#define int long long
int n, m;
void solve() {
std::cin >> n;
auto get_prime = [&](int x) -> std::vector<int> {
std::vector<int> res;
std::vector<bool> st(x + 1, false);
st[0] = st[1] = true;
for (int i = 2; i <= x; i++) {
if (!st[i]) {
res.emplace_back(i);
for (int j = i + i; j <= x; j += i) {
st[j] = true;
}
}
}
return res;
};
auto p = get_prime(sqrt(n / 12));
int m = p.size();
int ans = 0;
for (int i = 0; i < m; i++) {
for (int j = i + 1; j < m; j++) {
if (p[i] * p[i] * p[j] > n) break;
for (int k = j + 1; k < m; k++) {
if (p[i] * p[i] * p[j] * p[k] > n or
p[i] * p[i] * p[j] * p[k] * p[k] > n)
break;
ans++;
}
}
}
std::cout << ans << "\n";
}
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0), std::cout.tie(0);
std::cout << std::fixed << std::setprecision(15);
std::cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
solve();
return 0;
}