Hiểu bài toán

Bài toán yêu cầu đếm số cặp số nguyên dương (a, b) sao cho a ≤ n, b ≤ n và tích a * b = x. Nói cách khác, với một số nguyên dương x cho trước và giới hạn n, ta cần tìm số lượng cách chọn hai số nguyên dương không vượt quá n mà tích của chúng bằng x. Ví dụ, với n = 5, x = 6, các cặp (a, b) thỏa mãn là (1, 6) - không hợp lệ vì 6 > 5, (2, 3), (3, 2), (6, 1) - không hợp lệ. Chỉ có 1 cặp (2, 3) và (3, 2) nhưng coi như 2 cách nếu thứ tự có vai trò, nhưng trong các giải pháp thì (a, b) và (b, a) được xử lý riêng.

Các cách tiếp cận

Cách Duyệt các ước số (Factor Iteration)

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    freopen("mtable.inp","r",stdin);
    freopen("mtable.out","w",stdout);

    long long n, x;
    cin >> n >> x;

    long long cnt = 0;
    for (long long d = 1; d * d <= x; d++) {
        if (x % d == 0) {
            long long e = x / d;
            if (d <= n && e <= n) cnt++;
            if (d != e && e <= n && d <= n) cnt++;
        }
    }

    cout << cnt;
    return 0;
}

• Time Complexity: O(sqrt(x))
• Space Complexity: O(1)

Giải pháp này dựa trên việc phân tích x thành các thừa số nguyên tố. Nếu a * b = x, thì a và b phải là các ước của x. Do đó, ta chỉ cần duyệt qua tất cả các ước của x để tìm ra các cặp (a, b) thỏa mãn.

1. Duyệt i từ 1 đến sqrt(x).
2. Nếu i là ước của x (x % i == 0), thì i và x/i là một cặp ước của x.
3. Kiểm tra xem cả hai số i và x/i có đều nhỏ hơn hoặc bằng n không.
   • Nếu cả hai đều ≤ n, thì (i, x/i) là một cặp hợp lệ.
   • Nếu i ≠ x/i (tức là x không phải là số chính phương), thì (x/i, i) cũng là một cặp hợp lệ khác.
   • Lưu ý: Trong code, biến e = x/i. Nếu d và e đều ≤ n:
     • cnt++ cho cặp (d, e).
     • Nếu d != e, cnt++ cho cặp (e, d). Ví dụ: x=4, n=4. Các ước là 1, 2, 4. Duyệt d=1, e=4 -> 1≤4 và 4≤4 -> cnt=1, d!=e -> cnt=2 (các cặp (1,4) và (4,1)). Duyệt d=2, e=2 -> 2≤4 và 2≤4 -> cnt=3, d==e không tăng. Kết quả là 3. Các cặp là (1,4), (2,2), (4,1).

Cách Đếm ước số tối ưu (Optimized Counting)

#include <bits/stdc++.h>
using namespace std;

int n,x;
int kq=0;

int main() {
    freopen("mtable.inp","r",stdin);
    freopen("mtable.out","w",stdout);
    cin>>n>>x;
    if (x==1)cout<<1;
    else{
        if (n>=x)kq+=2;
        for(int i=2; i*i<=x; i++){
            if (x%i==0){
                if(n>=x/i){
                    if (i!=x/i)kq+=2;
                    else kq+=1;
                }
            }
        }
        cout<<kq;
    }
}

• Time Complexity: O(sqrt(x))
• Space Complexity: O(1)

Đây là một biến thể của giải pháp duyệt ước số, nhưng có một số điểm khác biệt trong cách xử lý các cặp đối xứng.

1. Xử lý trường hợp đặc biệt x=1: In ra 1 (cặp (1,1)).
2. Xử lý cặp (1, x) và (x, 1): Nếu n ≥ x, thì 1 và x đều ≤ n. Hai cặp này được thêm vào bằng kq += 2.
3. Duyệt i từ 2 đến sqrt(x) để tìm các ước còn lại.
4. Với mỗi ước i:
   • Kiểm tra x/i ≤ n (vì i ≥ 2 nên i ≤ n là hiển nhiên nếu x/i ≤ n? Không, cần kiểm tra cả i ≤ n).
   • Code kiểm tra if(n >= x/i). Nếu thỏa mãn:
     • Nếu i ≠ x/i, tăng 2 (cặp (i, x/i) và (x/i, i)).
     • Nếu i == x/i, tăng 1 (cặp (i, i)).

Lưu ý: Code này có vẻ bỏ qua kiểm tra i <= n một cách trực tiếp trong vòng lặp, nhưng vì i bắt đầu từ 2 và i*i <= x, nếu n nhỏ hơn i thì x/i sẽ lớn hơn i và có thể không thỏa mãn n >= x/i (trừ trường hợp x/i nhỏ). Tuy nhiên, logic này có thể sai nếu i > n nhưng x/i vẫn hợp lệ? Không, vì i > n thì (i, x/i) không hợp lệ. Nhưng code chỉ kiểm tra n >= x/i.

Ví dụ: n=2, x=4. i=2, x/i=2. i*i <= 4 (dừng ở 2). if(n >= x/i) -> 2>=2 true. i != x/i false. kq += 1. Ban đầu x=4, n>=x (2>=4) false. kq ban đầu 0. Kết quả 1. Đúng là (2,2).

Ví dụ: n=1, x=2. Vòng lặp i=2 không chạy (2*2 > 2). x!=1. if(n>=x) 1>=2 false. kq=0. Kết quả 0. Đúng.

Ví dụ: n=3, x=6. i=2, x/i=3. n>=3 true. i!=j true. kq+=2. i=3, x/i=2 (vòng lặp chỉ chạy đến sqrt(6)~2.4, nên i=2 là bước cuối). kq=2. Ban đầu n>=6 false. Kết quả 2. Đúng là (2,3) và (3,2).

Giải pháp này tối ưu ở chỗ xử lý riêng cặp (1, x) và chỉ duyệt từ 2.

Cách Duyệt theo trục (Coordinate Iteration)

#include <iostream>
using namespace std;

int main() {
    // Pseudocode for logic, actual implementation needs optimization
    // Logic: Count pairs (a, b) such that a*b = x
    // This is equivalent to iterating 'a' from 1 to min(n, x).
    long long n, x;
    cin >> n >> x;
    long long cnt = 0;
    for (long long a = 1; a <= n && a <= x; ++a) {
        if (x % a == 0) {
            long long b = x / a;
            if (b <= n) {
                cnt++; // Found pair (a, b)
            }
        }
    }
    cout << cnt;
    return 0;
}

• Time Complexity: O(min(n, x))
• Space Complexity: O(1)

Đây là cách tiếp cận trực quan nhất: duyệt qua tất cả các giá trị có thể của a.

1. Duyệt a từ 1 đến min(n, x).
2. Với mỗi a, kiểm tra xem a có phải là ước của x không (x % a == 0).
3. Nếu có, tính b = x / a.
4. Kiểm tra xem b có nhỏ hơn hoặc bằng n không.
5. Nếu b <= n, thì (a, b) là một cặp hợp lệ.

Giải pháp này chậm hơn đáng kể nếu n và x lớn (ví dụ 10^9), vì nó chạy trong thời gian tuyến tính O(n). Trong khi các giải pháp khác chạy trong thời gian O(sqrt(x)). Tuy nhiên, nó đúng về mặt logic và dễ hiểu. Các giải pháp được cung cấp trong bài nộp không sử dụng phương pháp này do độ phức tạp cao.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Vấn đề chỉ xoay quanh các ước của x. Nếu a * b = x, thì a và b phải là các ước của x.
• Số lượng các ước của một số x rất ít, chỉ tối đa khoảng 2*sqrt(x). Do đó, duyệt qua các ước của x là cách hiệu quả nhất.
• Cần phân biệt rõ giữa (a, b) và (b, a) nếu a != b, và xử lý trường hợp a = b (khi x là số chính phương).

Lỗi thường gặp

• Quên kiểm tra điều kiện a <= n và b <= n cho mỗi cặp ước tìm được.
• Xử lý sai số chính phương: Ví dụ x=4, ước là 1, 2, 4. Cặp (2, 2) chỉ được tính 1 lần, không được tính 2 lần như (1, 4) và (4, 1).
• Sử dụng biến số nguyên nhỏ (int) cho n và x có thể gây tràn số (overflow) nếu n và x lên tới 10^9 (tích có thể lên tới 10^18). Cần dùng long long.
• Trong giải pháp 'Đếm ước số tối ưu', cần chú ý việc kiểm tra điều kiện i <= n và x/i <= n. Code mẫu của Solution 3 có vẻ đã tối ưu hóa việc này bằng cách chỉ duyệt i từ 2 và kiểm tra n >= x/i, nhưng logic này dựa vào giả định rằng i nhỏ thì x/i lớn, nên việc kiểm tra n >= x/i là đủ. Tuy nhiên, một cách an toàn hơn nên kiểm tra cả hai. Solution 1 và 2 kiểm tra rõ ràng if (i <= n && j <= n).