Bedao FLOWERS Hay Không? Hay Hay

Điểm: 0,30 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

Input: stdin

Output: stdout

Tác giả:

bedao

Dạng bài

Ngôn ngữ cho phép

C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Có lẽ sau một thời gian rất dài chỉ ngồi coding, Lộkk cảm thấy thực sự căng thẳng và mệt mỏi. Vì vậy hôm nay Lộkk quyết định chọn ra một hoạt động mới giúp Lộkk cảm thấy thư giãn hơn. Lộkk ngồi đắn đo suy nghĩ. Các môn thể thao thì thực sự rất vui, nhưng mọi người cũng phải ở nhà hết rồi! Nếu chuyển qua chơi game, vậy cũng không khác nào ngồi coding với máy tính cả.

Lộkk quyết định chia sẻ những đắn đo này với Nhật, và Nhật gợi ý rằng: "Hay là làm vườn? Làm vườn tốt cho sức khỏe. Làm vườn ở ngoài trời, làn da tiếp xúc với ánh nắng có thể giúp có thể tăng cường Vitamin D. Làm vườn cũng giúp giảm huyết áp nè. Ngoài ra đây cũng là hoạt động nhẹ nhàng, giúp giảm căng thẳng rất hiệu quả!"

Lộkk thấy ý tưởng của Nhật quả là tuyệt vời, vì vậy Lộkk đã quyết định tạo ra một vườn hoa của riêng mình. Vườn hoa mà Lộkk định trồng có dạng một hình chữ nhật có kích thước $n \times m$ . Hình chữ nhất được chia thành các hàng và cột, với các hàng được đánh số từ $1$ đến $n$ từ trên xuống dưới và các cột được đánh số từ $1$ đến $m$ từ trái qua phải. Ô ở hàng thứ $r$ và cột thứ $c$ được thể hiện bởi cặp số $(r, c)$ .

Là người yêu thích toán học, nên Lộkk muốn khu vườn của mình cũng có tính chất đặc biệt. Lộkk chỉ trồng hoa vào các ô $(r, c)$ nếu như $r + c$ là số nguyên tố.

Cho kích thước khu vườn của Lộkk, hãy giúp Lộkk tìm xem Lộkk cần phải trồng bao nhiêu bông hoa trong khu vườn nhé!

Input

Gồm một dòng duy nhất chứa hai số nguyên $n$ và $m$ $(1 \leq n, m \leq 10^{6})$ là kích thước khu vườn của Lộkk.

Output

In ra một số nguyên duy nhất là số bông hoa mà Lộkk cần trồng.

Sample Input 1

Copy

5 5

Sample Output 1

Copy

Sample Input 2

Copy

10 7

Sample Output 2

Copy

Note

Dưới đây là hình minh họa cho hai test ví dụ.

Minh họa cho ví dụ một

Minh họa cho ví dụ hai

Bình luận

Hãy đọc nội quy trước khi bình luận.

1

Groot đã bình luận 6:59:35 ch, 30/06/2024

Gợi ý:

Sàng nguyên tố với giới han là MAX = 2e6

tạo 2 mảng f, g với ý nghĩa:

f[i] là số lượng nguyên tố của 1 hàng trong đoạn từ 2 đến i

for (int i = 2; i <= MAX; i++) f[i] = f[i-1] + (prime[i] ? 1 : 0);

g[i] là số lượng số nguyên tố của các hàng trong đoạn từ 2 -> i

for (int i = 2; i <= MAX; i++) g[i] = g[i-1] + f[i];

Kết quả

ans = g[m + n] - g[n] - g[m]

-9

hungkovietcode đã bình luận 1:44:20 sa, 04/01/2023

Ý tưởng: Việc đầu tiên là chúng ta cần tìm các số nguyên tố từ đến . Đ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 là .

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

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 nằm trên đường thẳng 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à và .

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ố tương ứng của mỗi điểm đã duyệt qua.

Khi với mỗi số nguyên tố , 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à , và cho việc duyệt các điểm ở biên là , vậy độ phức tạp tổng thể là .

Dưới đây là một cách triển khai cho thuật toán:

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.