🔗 UVA-10539 Almost Prime Numbers

題意

準質數(Almost Prime Numbers) 是指那些 非質數 且只能被單一質數整除的數字。具體而言，若一個整數可以表示成 pkp^k 的形式，其中 pp 是質數，kk 是正整數，且 k>1k > 1，則該整數為準質數。

給定一個正整數 nn ，表示有 nn 組測資，每組測資包含兩個整數 lowlow 和 highhigh，請輸出在範圍 [low,high][low, high] 內有多少個準質數。

約束條件

  • 1≤n≤6001 \leq n \leq 600
  • 0<low≤high<10120 < low \leq high < 10^{12}

LuckyCat 的中文翻譯

若我們在詢問時能夠知道所有準質數，那麼我們只需要在詢問時對排序後的所有準質數進行二分搜尋，就能夠知道在 [low,high][low, high] 內有多少個準質數。

故我們可以 預處理 所有準質數，並將其排序。而根據準質數的定義，我們需要先找出所有可能構成範圍內準質數的質數。雖然 101210^{12} 的範圍很大，但由於質數本身不是準質數，因此最大能構成準質數的質數 pp 滿足 p2≤1012p^2 \leq 10^{12}，故我們只需要找出所有小於等於 1012=106\sqrt{10^{12}} = 10^6 的質數即可。

這裡使用 埃氏篩(Sieve of Eratosthenes) 找出所有小於等於 10610^6 的質數。主要思路為將所有質數的倍數標記為非質數，最後剩下的就是質數，具體過程不再贅述。

在找到所有質數後，我們可以從 k=2k = 2 開始，將所有質數的 kk 次方加入準質數列表 almost_primesalmost\_primes 中，直到 pk>1012p^k > 10^{12} 為止。最後對 almost_primesalmost\_primes 進行排序。

在回答詢問時，我們只需要對排序後的準質數列表進行二分搜尋，就能夠知道在 [low,high][low, high] 內有多少個準質數。

複雜度分析

  • 時間複雜度：O(nlog⁡M+Nlog⁡log⁡N)\mathcal{O}(n \log M + \sqrt{N} \log \log \sqrt{N})，其中 nn 為詢問數量，NN 為最大數字範圍，MM 為準質數數量。
    • 埃氏篩的時間複雜度為 O(Nlog⁡log⁡N)\mathcal{O}(\sqrt{N} \log \log \sqrt{N})。
    • 生成準質數的時間複雜度為 O(M)\mathcal{O}(M)。（此乃廢話）
    • 每次二分搜尋的時間複雜度為 O(log⁡M)\mathcal{O}(\log M)。
  • 空間複雜度：O(N+M)\mathcal{O}(\sqrt{N} + M)
    • 需要額外的空間來存儲埃氏篩的列表和準質數列表。

對於每一個質數 pp，其對準質數的貢獻為 ⌊log⁡pN⌋−1\left\lfloor \log_p N \right\rfloor - 1，因此準質數的數量 MM 為 ∑p∈prime and p2≤N(⌊log⁡pN⌋−1)\displaystyle\sum_{p \in \text{prime and } p^2 \leq N} ( \left\lfloor \log_p N \right\rfloor - 1)。

由於準質數的數量很難估計，因此請恕我直接使用 MM 表示準質數的數量。根據 Claude Sonnet 3.5 的回答，準質數的數量約為 Nlog⁡N\frac{\sqrt{N}}{\log N}。以本題來說，實際的 M=80070<Nlog⁡N=83333.33M = 80070 < \frac{\sqrt{N}}{\log N} = 83333.33。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
from math import isqrt
from bisect import bisect_left, bisect_right

MAXN = int(1e12)
MAXN_SQRT = isqrt(MAXN)
is_prime = [True] * (MAXN_SQRT + 1)
is_prime[0] = is_prime[1] = False
for i in range(2, MAXN_SQRT + 1):
    if is_prime[i]:
        for j in range(i * i, MAXN_SQRT + 1, i):
            is_prime[j] = False

almost_primes = []
for i in range(2, MAXN_SQRT + 1):
    if is_prime[i]:
        x = i * i
        while x <= MAXN:
            almost_primes.append(x)
            x *= i
almost_primes.sort()

t = int(input())
for _ in range(t):
    lo, hi = map(int, input().split())
    print(bisect_right(almost_primes, hi) - bisect_left(almost_primes, lo))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const LL MAXN = 1e12;
const LL MAXN_SQRT = sqrt(MAXN);
#define endl '\n'
#define all(x) x.begin(), x.end()

vector<LL> almost_primes;
vector<bool> is_prime(MAXN_SQRT + 1, true);

void init() {
    is_prime[0] = is_prime[1] = false;
    for (LL i = 2; i * i <= MAXN_SQRT; i++) {
        if (is_prime[i]) {
            for (LL j = i * i; j <= MAXN_SQRT; j += i) {
                is_prime[j] = false;
            }
        }
    }
    for (LL i = 2; i <= MAXN_SQRT; i++) {
        if (is_prime[i]) {
            LL x = i * i;
            while (x <= MAXN) {
                almost_primes.push_back(x);
                x *= i;
            }
        }
    }
    sort(all(almost_primes));
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    init();
    int t;
    cin >> t;
    while (t--) {
        LL lo, hi;
        cin >> lo >> hi;
        cout << upper_bound(all(almost_primes), hi) - lower_bound(all(almost_primes), lo) << endl;
    }
    return 0;
}

類題

寫在最後

PROMPT

masterpiece, best quality, high quality, extremely detailed CG unity 8k wallpaper, extremely detailed, High Detail, vibrant colors, backlight, photo background,

(1girl, solo), Frieren, frieren, long hair, very long hair, (green eyes:1.5), grey hair, pointy ears, elf,

dress, white dress, sleeveless, sleeveless dress, jewelry, earrings, bare shoulders, parted bangs, bare arms, barefoot, bare legs, collarbone, looking at viewer, blush, sitting, closed mouth, full body, flower, water, wariza, strap slip, between legs, hand between legs, lily pad,

anime girl, sitting in water, white dress, pointed ears, floating flowers, serene, fantasy, soft lighting, dreamy atmosphere,

題目敘述不太直觀，需要看範例輸出入才能猜出 Almost Prime Numbers 的定義。

另外，這次 CPE 的最後兩題也太難了吧 QQ