Tóm tắt đề bài

Cho số nguyên dương \(k\) (\(1 \le k \le 10^{12}\)). Hãy đếm số cặp số nguyên dương \((a,b)\) thỏa mãn:

• \(a < b\)
• \(a \cdot b \le k\)

Phân tích

• Nếu cố duyệt mọi \(a,b\) thì không thể vì \(k\) lớn tới \(10^{12}\).
• Với một \(a\) cố định, các giá trị \(b\) thỏa \(a\cdot b \le k\) là:

• Đồng thời cần \(b \ge a+1\) do điều kiện \(a < b\).
• Vậy số lượng \(b\) hợp lệ ứng với \(a\) là:

• Ta chỉ cần xét \(a\) đến khi \(a(a+1) \le k\) (tồn tại ít nhất một \(b \ge a+1\)). Xấp xỉ \(a \le \sqrt{k}\), tức tối đa \(10^6\) vòng lặp — hoàn toàn ổn.

Hướng giải quyết

Ý tưởng

Duyệt \(a\) từ \(1\) trở lên. Với mỗi \(a\), tính \(t = \left\lfloor \frac{k}{a} \right\rfloor\) là \(b\) lớn nhất có thể. Khi đó:

• Nếu \(t \le a\) thì không có \(b > a\) nào thỏa mãn, ta có thể dừng luôn (vì \(a\) tăng thì \(t\) không tăng).
• Ngược lại, có đúng \(t-a\) giá trị \(b\) là \(a+1, a+2, \dots, t\).

Thuật toán

1. Đọc \(k\).
2. Khởi tạo ans = 0.
3. Với \(a\) chạy từ \(1\) đến khi dừng:
4. Tính \(t = k / a\) (chia nguyên).
5. Nếu $t <= athìbreak`.
6. Cộng ans += (t - a).
7. In ans.

Lưu ý / Pitfall

• Kết quả có thể khá lớn (xấp xỉ \(O(k)\) khi \(k\) lớn), cần dùng 64-bit (long long), thậm chí an toàn nhất là __int128 khi cộng dồn (dù với \(k \le 10^{12}\) thì long long vẫn đủ).
• Điều kiện dừng đúng là t <= a (tương đương \(\lfloor k/a \rfloor \le a\)).

Độ phức tạp

• Thời gian: \(O(\sqrt{k})\) (tối đa khoảng \(10^6\) lần lặp khi \(k = 10^{12}\))
• Bộ nhớ: \(O(1)\)

Code tham khảo

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

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

    long long k;
    cin >> k;

    __int128 ans = 0; // dùng __int128 để cực kỳ an toàn khi cộng dồn
    for (long long a = 1; ; a++) {
        long long t = k / a;      // b lớn nhất sao cho a*b <= k
        if (t <= a) break;        // không còn b > a nào thỏa
        ans += (t - a);           // b = a+1 .. t
    }

    // In __int128
    long long out = (long long)ans; // với k <= 1e12 thì vẫn vừa long long
    cout << out << "\n";
    return 0;
}