Hướng giải của Đếm số lượng ước số

Nhớ rằng hướng dẫn giải này chỉ nên sử dụng khi bế tắc, và tuyệt đối không nên sao chép mã nguồn kèm theo. Hãy tôn trọng tác giả bài tập và người viết hướng dẫn giải.
Nộp mã nguồn lời giải chính thức trước khi giải bài tập đó có thể khiến bạn bị ban.

Ý tưởng 1 (phân tích thừa số): N = p1^a1 p2^a2 ... thì số ước = (a1+1)(a2+1)... Ý tưởng 2 (sàng): Dùng sàng để tính trước số ước cho tất cả số từ 1 đến N.

C++ - Factorize

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int ans = 1;
    for (int i = 2; i  i <= n; i++) {
        int cnt = 0;
        while (n % i == 0) {
            n /= i;
            cnt++;
        }
        ans = (cnt + 1);
    }
    if (n > 1) ans *= 2;
    cout << ans << endl;
    return 0;
}

C++ - Sieve

#include <iostream>
#include <vector>
using namespace std;

const int MAX = 1000000;
vector<int> divcnt(MAX + 1, 0);

void sieve_divcnt() {
    for (int i = 1; i <= MAX; i++)
        for (int j = i; j <= MAX; j += i)
            divcnt[j]++;
}

int main() {
    sieve_divcnt();
    int n;
    cin >> n;
    cout << divcnt[n] << endl;
    return 0;
}

Python - Factorize

n = int(input())
ans = 1
i = 2
while i  i <= n:
    cnt = 0
    while n % i == 0:
        n //= i
        cnt += 1
    ans = (cnt + 1)
    i += 1
if n > 1:
    ans *= 2
print(ans)

Python - Sieve

MAX = 1000000
div = [0] * (MAX + 1)

for i in range(1, MAX + 1):
    for j in range(i, MAX + 1, i):
        div[j] += 1

n = int(input())
print(div[n])

Nhận xét

Không có ý kiến tại thời điểm này.