Ý tưởng

Việc đầu tiên là chúng ta cần tìm các số nguyên tố từ ~1~ đến ~n + m~. Điều này hoàn toàn làm được với thuật toán sàng số nguyên tố cơ bản vì giới hạn của ~n + m~ là ~2\times 10^6~.

Khi đã biết mọi số nguyên tố từ ~1~ đến ~n + m~, bài toán có thể phát biểu lại thành với mỗi số nguyên tố ~p~ nằm trong khoảng từ ~1~ đến ~n + m~, có bao nhiêu ô mà ~r + c = p~.

Nếu ta chuyển bài toán này thành bài toán hình học, đây là bài toán tìm giao của đường thẳng với hình chữ nhật. Cụ thể là ta cần tìm xem có bao nhiêu điểm nguyên ~(x, y)~ nằm trên đường thẳng ~x + y = p~ và nằm trong hình chữ nhật song song với trục tọa độ có tọa độ hai đỉnh của một đường chéo là ~(1, 1)~ và ~(n, m)~.

Bài toán này có nhiều cách làm với nhiều công thức. Tuy nhiên mọi cách đều có quy về việc tìm giao của đường thẳng với biên của hình chữ nhật. Với giới hạn của bài toán đã cho, ta có thể duyệt qua mọi điểm trên biên và tìm số nguyên tố ~p~ tương ứng của mỗi điểm đã duyệt qua.

Khi với mỗi số nguyên tố ~p~, ta tìm được giao điểm với biên của hình chữ nhật, ta có thể suy ra được số lượng điểm nguyên nằm giữa hai điểm này.

Về mặt triển khai, có thể thay việc tìm điểm nguyên bằng việc tìm hoành độ hoặc tung độ của giảo điểm, vì số điểm nằm giữa hai giao điểm bằng sai khác giữa hai hoành độ cộng với 1, và cũng bằng sai khác giữa hai tung độ cộng với một.

Độ phức tạp cho việc sàng thông thường là ~O\left((n + m) \log (n + m) \right)~, và cho việc duyệt các điểm ở biên là ~O(n + m)~, vậy độ phức tạp tổng thể là ~O\left( (n + m) \log (n + m) \right)~.

Code mẫu

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

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

    int max_val = n + m;

    vector<bool> is_prime(max_val + 1, true);
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i <= max_val; ++i) {
        if (!is_prime[i]) continue;
        if (1ll * i * i > max_val) continue;
        for (int f = i * i; f <= max_val; f += i)
            is_prime[f] = false;
    }

    vector<int> lower_row(max_val + 1), upper_row(max_val + 1);
    for (int row = 1; row <= n; ++row) {
        if (is_prime[row + 1]) upper_row[row + 1] = row;
        if (is_prime[row + m]) lower_row[row + m] = row;
    }
    for (int col = 1; col <= m; ++col) {
        if (is_prime[col + 1]) lower_row[col + 1] = 1;
        if (is_prime[col + n]) upper_row[col + n] = n;
    }

    long long ans = 0;
    for (int num = 1; num <= max_val; ++num) {
        if (!is_prime[num]) continue;
        ans += upper_row[num] - lower_row[num] + 1;
    }
    cout << ans;

    return 0;
}