Bài 9.5. Mạng Lưới Giao Thương Thiên Hà "Phi-Tổng" - [Độ khó: Khó]

Liên minh Thiên hà đang cố gắng xây dựng một mạng lưới giao thương phức tạp giữa các hành tinh. Mỗi hành tinh được gán một ID duy nhất là một số nguyên dương. Để đánh giá sự "độc đáo" và "tương thích" của một hành tinh trong mạng lưới, các nhà khoa học đã định nghĩa một "chỉ số độc đáo" cho hành tinh có ID i là phi(i) (Euler's Totient function). Hàm phi(i) đếm số lượng các số nguyên dương nhỏ hơn hoặc bằng i mà nguyên tố cùng nhau với i.

Để xác định độ ổn định và tiềm năng phát triển của toàn bộ mạng lưới gồm N hành tinh đầu tiên (từ ID 1 đến N), bạn được yêu cầu tính tổng tất cả các chỉ số độc đáo của các hành tinh đó, tức là, tính sum(phi(i)) với i từ 1 đến N. Vì N có thể rất lớn, bạn cần một phương pháp tính toán hiệu quả.

INPUT FORMAT

Một dòng duy nhất chứa một số nguyên N (1 <= N <= 10^7).

OUTPUT FORMAT

In ra một số nguyên duy nhất là tổng sum(phi(i)) với i từ 1 đến N.

Ví dụ:

Input:

6

Output:

18

Giải thích:

• N = 6. Chúng ta cần tính phi(1) + phi(2) + phi(3) + phi(4) + phi(5) + phi(6).
• phi(1) = 1 (chỉ có 1 là nguyên tố cùng nhau với 1).
• phi(2) = 1 (chỉ có 1 là nguyên tố cùng nhau với 2).
• phi(3) = 2 (1, 2 là nguyên tố cùng nhau với 3).
• phi(4) = 2 (1, 3 là nguyên tố cùng nhau với 4).
• phi(5) = 4 (1, 2, 3, 4 là nguyên tố cùng nhau với 5).
• phi(6) = 2 (1, 5 là nguyên tố cùng nhau với 6).
• Tổng = 1 + 1 + 2 + 2 + 4 + 2 = 12.

Giải thích lại cho ví dụ 6 để khớp với output 18:

• Có lẽ có một lỗi trong tính toán ví dụ của tôi.
• phi(1) = 1
• phi(2) = 1
• phi(3) = 2
• phi(4) = 2
• phi(5) = 4
• phi(6) = 2
• Tổng là 1+1+2+2+4+2 = 12. Nếu output là 18, có lẽ tôi đã nhầm N hoặc công thức.
• Ah, sum(phi(i)) from i=1 to `N is a known identity: sum(phi(i) for i in 1..N) = sum(d * (N/d) for d in 1..N if d is divisor). No, that's not it.
• The example output 18 is for N=8 usually.
• For N=6, sum phi(i) is 12. Let's adjust example output.
• Adjusted Example Output for N=6: Input:

    6

  Output:

    12

  Giải thích:
  • N = 6. Chúng ta cần tính phi(1) + phi(2) + phi(3) + phi(4) + phi(5) + phi(6).
  • phi(1) = 1 (số 1 là nguyên tố cùng nhau với 1).
  • phi(2) = 1 (số 1 là nguyên tố cùng nhau với 2).
  • phi(3) = 2 (các số 1, 2 là nguyên tố cùng nhau với 3).
  • phi(4) = 2 (các số 1, 3 là nguyên tố cùng nhau với 4).
  • phi(5) = 4 (các số 1, 2, 3, 4 là nguyên tố cùng nhau với 5).
  • phi(6) = 2 (các số 1, 5 là nguyên tố cùng nhau với 6).
  • Tổng phi(i) từ 1 đến 6 là: 1 + 1 + 2 + 2 + 4 + 2 = 12. (Gợi ý: Để giải quyết bài toán này hiệu quả với N lên đến 10^7, bạn cần sử dụng một biến thể của Sàng Eratosthenes để tính trước giá trị phi(i) cho tất cả các i từ 1 đến N trong thời gian tuyến tính hoặc gần tuyến tính. Sau đó, tính tổng lũy tiến (prefix sum) để trả lời nhanh chóng.)