Count Divisors

Điểm: 100,00

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

Input: stdin

Output: stdout

Tác giả:

hieuhoccode

Dạng bài

Hiếu là một học sinh "xuất sắc" tại một trường Tiểu học (có thể là top 1 từ dưới lên🤡). Vào một ngày đẹp trời trong tuần, Hiếu đến lớp và được học về khái niệm "giai thừa" và cách tính số lượng ước nguyên dương của một số. Vì Hiếu rất giỏi, những kiến thức này không thể làm khó Hiếu được. Vậy nên, Hiếu đã nảy ra một câu hỏi thú vị: "Giai thừa của số n sẽ có bao nhiêu ước nguyên dương?"

Tuy nhiên, bài toán này không hề dễ dàng, và với kỹ năng còn non nên Hiếu chưa thể giải được. Các bạn hãy giúp Hiếu giải bài toán này nhé!!!!

Input:

Một dòng duy nhất chứa số nguyên dương n (1 ≤ n ≤ 10⁴).

Output:

Số lượng ước nguyên dương của n! (giai thừa của n). Kết quả có thể rất lớn, nên hãy in ra phần dư khi chia cho 10⁹ + 7.

Sample Input

Sample Output

Bình luận

Hãy đọc nội quy trước khi bình luận.

endgame1462005 đã bình luận lúc 2, Tháng 2, 2025, 1:48

include <bits/stdc++.h>

using namespace std;

vector<int> freq; vector<bool> dp; vector<int> primes;

void fact(int i) { for (int p : primes) { if (p * p > i) break; while (i % p == 0) { ++freq[p]; i /= p; } } if (i > 1) ++freq[i]; // Nếu còn lại số nguyên tố }

int main() { int n; cin >> n;

// Sàng Eratosthenes để tìm số nguyên tố
dp.assign(n + 1, true);
dp[0] = dp[1] = false;
for (int p = 2; p * p <= n; ++p) {
    if (dp[p]) {
        for (int i = p * p; i <= n; i += p) 
            dp[i] = false;
    }
}

// Lưu danh sách số nguyên tố
for (int i = 2; i <= n; ++i) {
    if (dp[i]) {
        primes.push_back(i);
    }
}

// Khởi tạo tần suất xuất hiện của số nguyên tố
freq.assign(n + 1, 0);

// Phân tích thừa số nguyên tố của tất cả các số từ 1 đến n
for (int i = 1; i <= n; ++i) {
    fact(i);
}

// Tính số ước của n!
long long divisors = 1;
for (int p : primes) {
    if (freq[p] > 0) {
        divisors *= (freq[p] + 1);
    }
}

cout << divisors << endl;

return 0;

}