Tác giả:
Reviewer:
Để có thể hiểu được toàn bộ bài này, bạn nên nắm vững kiến thức và cài đặt được:
Đề bài: Cho một số nguyên dương . Đếm số ước của .
Với nhiều coder, đây là một trong những bài toán beginner không thể không làm qua. Đây là bài toán thường được sử dụng như một ví dụ về việc phải tìm cách để tối ưu số lần lặp.
Giải thuật ngây thơ nhất rất đơn giản: từ nhận xét mọi ước của đều không vượt quá , ta duyệt mọi số nguyên dương trong đoạn và đếm số lượng ước của trong đó:
int divCount(int n) {
int ret = 0;
for (int i = 1; i <= n; i ++)
ret += (n % i == 0);
return ret;
}
Ta nhận thấy rằng chỉ cần duyệt các ước tới là đủ, do ứng với mọi ước của nhỏ hơn ta có hai ước của là và , và khi là số chính phương, ứng với ước ta có một ước duy nhất là chính nó.
Chứng minh
Gọi là một ước của , khi đó tồn tại một số nguyên sao cho . Nếu , khi đó ta có . Trường hợp , không mất tính tổng quát ta giả sử . Dễ thấy , vì nếu thì ta có và nếu thì , đều mâu thuẫn với giả thiết .
int divCount(long long n) {
int ret = 0;
for (int i = 1; 1ll * i * i <= n; i ++) {
ret += 2 * (n % i == 0);
if (1ll * i * i == n) ret --;
}
return ret;
}
Hai giải thuật trên có độ phức tạp thời gian lần lượt là và , sẽ chạy tốt với và . Rất khó để cải thiện độ phức tạp này để phù hợp với lớn hơn.
Định lý: Nếu một số được phân tích ra thừa số nguyên tố thành:
với là các số nguyên tố, là các số nguyên dương thì số ước của là:
(Chữ đọc là tau).
Mọi ước của khi phân tích thành thừa số nguyên tố sẽ có dạng:
với .
Mỗi cách chọn số ứng với một cách chọn bộ số nên số cách chọn thoả mãn là .
Để giải bài toán này theo cách phân tích ra thừa số nguyên tố, đầu tiên ta sử dụng sàng nguyên tố để lưu lại các số nguyên tố nhỏ hơn . Sau đó, lần lượt chia cho các số trên rồi thu lại số lần chia ứng với mỗi số; đó chính là số mũ của các thừa số nguyên tố tương ứng. Cuối cùng, áp dụng công thức trên để tính ra kết quả.
Cách làm này mất thời gian và không gian để chuẩn bị sàng, và thời gian để phân tích, với là số lượng số nguyên tố nhỏ hơn . Tổng độ phức tạp là .
Sử dụng nhận xét sau, ta giảm được độ phức tạp xuống . Ta viết . Trong đó, số là tích của tất cả các thừa số nguyên tố của đã nâng lên luỹ thừa có cơ số nhỏ hơn , còn . Xét hai trường hợp:
Ví dụ:
Khi cài đặt, sau khi chia cho toàn bộ các số nguyên tố đã thu được sau khi sàng, giá trị còn lại chính là .
Một edge case nho nhỏ là . Do không thể phân tích được thành thừa số nguyên tố, ta trả về luôn cho trường hợp này.
const int MAXN = 1e6;
vector<int> primes;
vector<bool> isPrime;
void sieve() {
isPrime.assign(MAXN + 1, 1);
isPrime[0] = isPrime[1] = 0;
for (int i = 2; i <= MAXN; i++) {
if (!isPrime[i]) continue;
primes.push_back(i);
for (int j = i + i; j <= MAXN; j += i) {
isPrime[j] = 0;
}
}
}
int countDiv(long long n) {
if (n == 1) return 1;
vector<int> powV;
for (auto p : primes) {
int cnt = 0;
while (n % p == 0) {
n /= p;
++cnt;
}
if (cnt) powV.push_back(cnt);
}
if (n != 1) powV.push_back(1);
int ret = 1;
for (auto i : powV) ret *= (i + 1);
return ret;
}
void solution() {
sieve();
long long n;
cin >> n;
cout << countDiv(n);
}
Cho tới bước này, ta có thể giải được bài toán với . Ta sẽ cải tiến để bài toán giải được với , với độ phức tạp là khoảng .
Vẫn viết dưới dạng như trên, được định nghĩa tương tự như trên, chỉ khác giới hạn các thừa số nguyên tố lúc này là : . Lúc này ta không thể chắc chắn là số nguyên tố nữa. Tuy nhiên, lại chỉ có thể thuộc vào một trong bốn trường hợp:
Các trường hợp khác:
Để kiểm tra trường hợp thứ nhất, ta có thể dùng thuật toán Rabin-Miller. Để kiểm tra trường hợp thứ hai, ta kiểm tra xem có phải số chính phương không. Các số còn lại sẽ rơi vào trường hợp thứ ba.
const int MAXN = 1e6;
vector<int> primes;
vector<bool> isPrime;
void sieve() {
isPrime.assign(MAXN + 1, 1);
isPrime[0] = isPrime[1] = 0;
for (int i = 2; i <= MAXN; i++) {
if (!isPrime[i]) continue;
primes.push_back(i);
for (int j = i + i; j <= MAXN; j += i) {
isPrime[j] = 0;
}
}
}
long long binaryPower(long long a, long long k, long long n) {
a = a % n;
long long res = 1;
while (k) {
if (k & 1)
res = (res * a) % n;
a = (a * a) % n;
k /= 2;
}
return res;
}
bool test(long long a, long long n, long long k, long long m) {
long long mod = binaryPower(a, m, n);
if (mod == 1 || mod == n - 1)
return 1;
for (int l = 1; l < k; ++l) {
mod = (mod * mod) % n;
if (mod == n - 1)
return 1;
}
return 0;
}
bool isPrimeRabinMiller(long long n) {
vector<int> checkSet = {2, 3, 5, 7,
11, 13, 17, 19,
23, 29, 31, 37};
if (n <= 37) {
for (int i : checkSet) {
if (i == n) return 1;
}
return 0;
}
long long k = 0, m = n - 1;
while (m % 2 == 0) {
m /= 2;
k++;
}
for (auto a : checkSet)
if (!test(a, n, k, m))
return 0;
return 1;
}
bool isSquare(long long n){
long long c = sqrt(n + 4);
return c * c == n || (c - 1) * (c - 1) == n;
}
int countDiv(long long n) {
if (n == 1) return 1;
vector<int> powV;
for (auto p : primes) {
int cnt = 0;
while (n % p == 0) {
n /= p;
++cnt;
}
if (cnt) powV.push_back(cnt);
}
if (n != 1) {
if (isPrimeRabinMiller(n)) powV.push_back(1);
else if (isSquare(n)) powV.push_back(2);
else {
powV.push_back(1);
powV.push_back(1);
}
}
int ret = 1;
for (auto i : powV) ret *= (i + 1);
return ret;
}
void solution() {
sieve();
long long n;
cin >> n;
cout << countDiv(n);
}
Phần Rabin-Miller có độ phức tạp là . Phần kiểm tra số chính phương có độ phức tạp là , với chú ý rằng cần phải xét một vài số lân cận sqrt(N) để đưa ra kết quả chính xác. Tổng hợp lại, độ phức tạp của giải thuật trên là .
Giải thuật này thậm chí còn có thể tối ưu tới khoảng . Tuy vậy số trường hợp được đặt ra là tương đối lớn và kiểm tra chúng cũng không hề dễ dàng.
Ngoài ra, nếu có thể phân tích ra thừa số nguyên tố bằng thuật toán rho của Pollard, lời giải lúc này cũng có độ phức tạp là khoảng .
Đề bài: Cho truy vấn. Ở truy vấn thứ , cần tìm số các ước của số với .
Bằng cách duyệt qua mọi ước của từng số một, độ phức tạp thời gian sẽ là . Còn với cách thứ hai giống như ở trên, độ phức tạp tốt nhất là . Với nhỏ, ta hoàn toàn có thể làm tương tự như trên.
Khi đủ lớn và không quá lớn , các hướng làm trên tỏ ra khá tồi.
Với cách thứ hai, ta có thể thay đổi một chút để có thể đưa ra kết quả của truy vấn nhanh hơn. Khi chuẩn bị, với mỗi số , thay vì chỉ lưu isPrime[x], ta lưu lại ước nguyên tố nhỏ nhất của , là minPDiv[x]. Khi thực hiện truy vấn, thay vì chia cho toàn bộ các số nguyên tố, ta chỉ cần chia liên tục cho ước nguyên tố nhỏ nhất của nó tại thời điểm đó, ta sẽ dần thu được kết quả.
const int MAXN = 1e6;
vector<int> minPDiv;
void sieve() {
minPDiv.resize(MAXN + 1);
for (int i = 2; i <= MAXN; i++) {
if (minPDiv[i]) continue;
minPDiv[i] = i;
for (int j = i + i; j <= MAXN; j += i) {
minPDiv[j] = i;
}
}
}
int countDiv(int n) {
if (n == 1) return 1;
vector<int> powV;
int lastDiv = 0;
int cnt = 0;
while (n != 1) {
if (minPDiv[n] != lastDiv) {
if (cnt) powV.push_back(cnt);
cnt = 0;
}
++cnt;
lastDiv = minPDiv[n];
n /= minPDiv[n];
}
if (cnt) powV.push_back(cnt);
int ret = 1;
for (auto i : powV) ret *= (i + 1);
return ret;
}
void solution() {
sieve();
int q;
cin >> q;
while (q--) {
int n;
cin >> n;
cout << countDiv(n) << "\n";
}
}
Phần chuẩn bị sàng nguyên tố mất không gian và thời gian. Mỗi truy vấn, số phép tính được thực hiện bằng đúng tổng số mũ của các thừa số nguyên tố trong phân tích của . Dễ thấy giá trị này không vượt quá , và do đó độ phức tạp thời gian của phần này là . Độ phức tạp thời gian nói chung của cả giải thuật là .
Ta cũng có thể lưu lại thêm cả số mũ của ước nguyên tố nhỏ nhất cùng với ước đó của từng số. Cách làm này sẽ có độ phức tạp là thời gian, và tốn thêm không gian so với cách đã trình bày ở trên.
Đề bài: Cho một số nguyên dương . Tính: với là số ước của .
Thử áp dụng hai hướng giải quyết ở trên, ta thu được độ phức tạp lần lượt là và . Tuy vậy, bài toán này còn có một lời giải tốt hơn, có thời gian chạy dưới mức tuyến tính.
Dễ thấy với mỗi số , sẽ tồn tại bội của trong đoạn . Vì vậy, nếu liệt kê tất cả các ước của các số từ tới , số sẽ xuất hiện lần.
Do vậy, kết quả của bài toán sẽ trở thành:
Tổng trên có thể được tính một cách dễ dàng trong . Tuy nhiên, dựa vào nhận xét sau, ta có thể tối ưu tính toán xuống :
Nhận xét: Với , phép tính nhận giá trị khác nhau với mỗi giá trị của . Với , phép tính này nhận tổng cộng hoặc giá trị khác nhau, các giá trị này không vượt quá (Xem chứng minh nhận xét này tại đây).
Dựa vào nhận xét trên, ta chỉ cần tính tổng tới , còn lại với mỗi ta đếm xem có bao nhiêu lần giá trị này xuất hiện rồi cộng vào tổng tích luỹ.
long long accCountDiv(long long n) {
long long ret = 0;
for (int i = 1; 1ll * i * i <= n; i ++)
ret += n / i;
for (int i = 1; i < n / (int)sqrt(n); i ++)
ret += 1ll * (n / i - n / (i + 1)) * i;
return ret;
}
void solution() {
long long n;
cin >> n;
cout << accCountDiv(n);
}
Đề bài 1: Cho một số nguyên dương . Tính tổng các ước của .
Đề bài 2: Cho một số nguyên dương . Cho truy vấn. Ở truy vấn thứ , cần tìm tổng các ước của số với .
Một cách rất tự nhiên, ta có một lời giải đơn giản cho bài toán này giống như khi tìm số ước:
int divSum(int n) {
int ret = 0;
for (int i = 1; i * i <= n; i ++) {
ret += (i + n / i) * (n % i == 0);
if (i * i == n) ret -= i;
}
return ret;
}
Độ phức tạp thời gian của giải thuật trên là .
Tương ứng với cách thứ hai của bài toán trên, hàm tổng các ước cũng có một tính chất đặc biệt:
Định lý: Nếu một số được phân tích ra thừa số nguyên tố thành: với là các số nguyên tố, là các số nguyên dương thì tổng các ước của là:
Mọi ước của khi phân tích thành thừa số nguyên tố sẽ có dạng: $$d = \prod_{i = 1}{k}{p_i{\mu_i}}$$ với .
Ta có: $$\sigma(N) = \sum_{\mu_1=0}{m_1}{\sum_{\mu_2=0}{m_2}{\dots\sum_{\mu_k=0}{m_k}{(p_1{\mu_1}p_2^{\mu_2}\dots p_k^{\mu_k})}}}$$ $$\Rightarrow \sigma(N) = \sum_{\mu_1=0}{m_1}{p_1{m_1}}\times\sum_{\mu_2=0}{m_2}{p_2{m_2}}\times\dots\times\sum_{\mu_k=0}{m_k}{p_k{m_k}}$$ $$\Rightarrow \sigma(N) = \left(\frac{p_1{m_1+1}-1}{p_1-1}\right)\left(\frac{p_2{m_2+1}-1}{p_2-1}\right)\dots\left(\frac{p_k^{m_k+1}-1}{p_k-1}\right)$$ (do ) $$\Rightarrow \sigma(N) = \prod_{i = 1}{k}{\frac{p_i{m_i+1}-1}{p_i-1}}$$
Với tính chất này, ta dễ dàng sử dụng sàng nguyên tố để tính tích trên với từng thừa số nguyên tố. Tuỳ vào bài toán mà độ phức tạp phù hợp sẽ là hoặc .
Cải tiến không thể áp dụng để tính tổng do nó không cho ta biết cụ thể các ước. Tuy nhiên, bài toán tính tổng các ước của một số duy nhất cho trước vẫn có thể giải trong bằng thuật toán rho của Pollard.