Bài 5.4. Cặp Số Ma Thuật trong Dải - [Độ khó: Khó]

LÀM BÀI
Points: 10 (partial)
Time limit: 2.0s
Memory limit: 64M
Author:
baonguyen113
Problem type

Bài 5.4. Cặp Số Ma Thuật trong Dải - [Độ khó: Khó]

Trong một cuốn sách cổ bị thất lạc, một phép thuật cổ xưa được mô tả dựa trên "Cặp Số Ma Thuật". Một cặp số (A, B) được coi là ma thuật nếu thỏa mãn hai điều kiện:

  1. Tổng của chúng (A + B) là một số nguyên tố.
  2. Tích của chúng (A * B) là một số chính phương.

Bạn được giao nhiệm vụ tìm kiếm tất cả các cặp số ma thuật (A, B) trong một dải số cho trước [L, R], sao cho L <= A <= B <= R. Hãy đếm tổng số cặp số ma thuật tìm được.

Bài toán này đòi hỏi bạn phải sử dụng vòng lặp lồng nhau một cách hiệu quả, kết hợp với các hàm kiểm tra tính nguyên tố và tính chính phương, đây là những kỹ thuật cơ bản nhưng quan trọng trong lập trình thi đấu.

INPUT FORMAT

Dòng đầu tiên chứa hai số nguyên L và R cách nhau bởi dấu cách.

  • L (1 <= L <= R): Giới hạn dưới của dải số.
  • R (1 <= R <= 1000): Giới hạn trên của dải số.
OUTPUT FORMAT

In ra một số nguyên duy nhất là tổng số cặp số ma thuật tìm được.

Ví dụ:

Input:

1 10

Output:

4

Giải thích: Dải số là [1, 10]. Chúng ta cần tìm các cặp (A, B) sao cho 1 <= A <= B <= 10.

Các cặp số (A, B) thỏa mãn:

  • (1, 3):
    • A + B = 1 + 3 = 4 (không phải số nguyên tố).
  • (1, 8):
    • A + B = 1 + 8 = 9 (không phải số nguyên tố).
  • (2, 2):
    • A + B = 2 + 2 = 4 (không phải số nguyên tố).
  • (2, 8):
    • A + B = 2 + 8 = 10 (không phải số nguyên tố).
  • (4, 5):
    • A + B = 4 + 5 = 9 (không phải số nguyên tố).
  • (4, 9):
    • A + B = 4 + 9 = 13 (là số nguyên tố).
    • A * B = 4 * 9 = 36 (là số chính phương, 6 * 6 = 36).
    • => (4, 9) là một cặp ma thuật.
  • (5, 5):
    • A + B = 5 + 5 = 10 (không phải số nguyên tố).
  • (6, 6):
    • A + B = 6 + 6 = 12 (không phải số nguyên tố).
  • (7, 9):
    • A + B = 7 + 9 = 16 (không phải số nguyên tố).
  • (8, 8):
    • A + B = 8 + 8 = 16 (không phải số nguyên tố).
  • (9, 9):
    • A + B = 9 + 9 = 18 (không phải số nguyên tố).
  • (1, 15): (giả sử R lớn hơn, chỉ để ví dụ)
    • A + B = 1 + 15 = 16 (không nguyên tố).
  • (2, 18): (giả sử R lớn hơn)
    • A + B = 2 + 18 = 20 (không nguyên tố).

Wait, the example output 4 for 1 10 must have more pairs. Let's find some. Prime numbers up to 10+10 = 20: 2, 3, 5, 7, 11, 13, 17, 19. Perfect squares: 1, 4, 9, 16, 25, 36, 49, 64, 81, 100.

Let's list pairs (A, B) where 1 <= A <= B <= 10:

  1. (1, 1): Sum=2 (Prime), Prod=1 (Perfect Square). Magic!
  2. (1, 3): Sum=4 (Not Prime).
  3. (1, 8): Sum=9 (Not Prime).
  4. (2, 2): Sum=4 (Not Prime).
  5. (2, 8): Sum=10 (Not Prime).
  6. (3, 1): (Skipped because A <= B means (1, 3) was considered).
  7. (3, 3): Sum=6 (Not Prime).
  8. (4, 4): Sum=8 (Not Prime).
  9. (4, 9): Sum=13 (Prime), Prod=36 (Perfect Square). Magic!
  10. (5, 5): Sum=10 (Not Prime).
  11. (6, 6): Sum=12 (Not Prime).
  12. (7, 7): Sum=14 (Not Prime).
  13. (8, 2): (Skipped).
  14. (8, 8): Sum=16 (Not Prime).
  15. (9, 1): (Skipped).
  16. (9, 9): Sum=18 (Not Prime).

There seems to be only 2 magic pairs: (1, 1) and (4, 9). So 4 is still puzzling. What if A and B can be any integer, not necessarily within the range L to R, but their sum and product fall into these ranges? No, L <= A <= B <= R is clear.

Could the problem be asking for something like sqrt(A*B) must be an integer, and A+B must be prime? Yes, that's "perfect square".

Let's reconsider the definition. Maybe the problem setter's intention for "perfect square" is just that A and B themselves are squares? No, it clearly says A * B.

Let's search for more pairs from 1 to 10 that satisfy the conditions.

  • A=1:
    • B=1: Sum=2(P), Prod=1(PS). (1,1) is magic.
    • B=2: Sum=3(P), Prod=2(Not PS).
    • B=3: Sum=4(Not P).
    • B=4: Sum=5(P), Prod=4(PS). (1,4) is magic.
    • B=5: Sum=6(Not P).
    • B=6: Sum=7(P), Prod=6(Not PS).
    • B=7: Sum=8(Not P).
    • B=8: Sum=9(Not P).
    • B=9: Sum=10(Not P).
    • B=10: Sum=11(P), Prod=10(Not PS).
  • A=2:
    • B=2: Sum=4(Not P).
    • B=3: Sum=5(P), Prod=6(Not PS).
    • B=4: Sum=6(Not P).
    • B=5: Sum=7(P), Prod=10(Not PS).
    • B=6: Sum=8(Not P).
    • B=7: Sum=9(Not P).
    • B=8: Sum=10(Not P).
    • B=9: Sum=11(P), Prod=18(Not PS).
    • B=10: Sum=12(Not P).
  • A=3:
    • B=3: Sum=6(Not P).
    • B=4: Sum=7(P), Prod=12(Not PS).
    • B=5: Sum=8(Not P).
    • B=6: Sum=9(Not P).
    • B=7: Sum=10(Not P).
    • B=8: Sum=11(P), Prod=24(Not PS).
    • B=9: Sum=12(Not P).
    • B=10: Sum=13(P), Prod=30(Not PS).
  • A=4:
    • B=4: Sum=8(Not P).
    • B=5: Sum=9(Not P).
    • B=6: Sum=10(Not P).
    • B=7: Sum=11(P), Prod=28(Not PS).
    • B=8: Sum=12(Not P).
    • B=9: Sum=13(P), Prod=36(PS). Magic!
    • B=10: Sum=14(Not P).
  • A=5:
    • B=5: Sum=10(Not P).
    • B=6: Sum=11(P), Prod=30(Not PS).
    • B=7: Sum=12(Not P).
    • B=8: Sum=13(P), Prod=40(Not PS).
    • B=9: Sum=14(Not P).
    • B=10: Sum=15(Not P).
  • A=6:
    • B=6: Sum=12(Not P).
    • B=7: Sum=13(P), Prod=42(Not PS).
    • B=8: Sum=14(Not P).
    • B=9: Sum=15(Not P).
    • B=10: Sum=16(Not P).
  • A=7:
    • B=7: Sum=14(Not P).
    • B=8: Sum=15(Not P).
    • B=9: Sum=16(Not P).
    • B=10: Sum=17(P), Prod=70(Not PS).
  • A=8:
    • B=8: Sum=16(Not P).
    • B=9: Sum=17(P), Prod=72(Not PS).
    • B=10: Sum=18(Not P).
  • A=9:
    • B=9: Sum=18(Not P).
    • B=10: Sum=19(P), Prod=90(Not PS).
  • A=10:
    • B=10: Sum=20(Not P).

My count is 3 magic pairs: (1,1), (1,4), (4,9). The example output 4 is still off. I will use my calculated example and change output to 3. Consistency is more important than matching a possibly flawed example.

Comments

There are no comments at the moment.

Zalo