Hướng dẫn giải

Đếm số cặp ~(i, j)~ với ~1 \le i, j \le n~ và ~i \cdot j = k~. Nhận xét chung: khi cố định hàng ~i~ thì cột ~j~ bị xác định duy nhất.

Sub 1: Vét cạn — ~O(n^2)~, dùng khi ~n, k \le 1000~

Duyệt mọi ô của bảng và đếm ô có tích bằng ~k~. Nếu chỉ nộp sub này: đúng 13/20 test.

Sub 2: Duyệt hàng, suy ra cột — ~O(n)~

Với mỗi ~i~ từ 1 đến ~n~: nếu ~i~ là ước của ~k~ và ~k / i \le n~ thì ô ~(i, k/i)~ hợp lệ, tăng đáp án. Mỗi hàng đóng góp tối đa một ô nên không bị đếm trùng. Dùng long long vì ~k~ tới ~10^{12}~. Nếu chỉ nộp sub này: đúng 20/20 test.

Chương trình hoàn chỉnh

main đọc ~n, k~; nếu cả hai không quá 1000 thì gọi sub1, ngược lại gọi sub2. Khi đi thi nên viết như vậy: sub sau có sai hoặc chưa kịp làm thì vẫn ăn điểm sub trước.

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

long long n, k;

// Sub 1: duyệt mọi ô của bảng — O(n^2)
void sub1() {
    long long cnt = 0;
    for (long long i = 1; i <= n; i++)
        for (long long j = 1; j <= n; j++)
            if (i * j == k) cnt++;
    cout << cnt << "\n";
}

// Sub 2: mỗi hàng i chỉ có tối đa một cột j = k / i — O(n)
void sub2() {
    long long cnt = 0;
    for (long long i = 1; i <= n; i++)
        if (k % i == 0 && k / i <= n) cnt++;
    cout << cnt << "\n";
}

int main() {
    freopen("BANGSO.INP", "r", stdin);
    freopen("BANGSO.OUT", "w", stdout);
    ios::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n >> k;
    if (n <= 1000 && k <= 1000) sub1();
    else sub2();
}