Bài 33.5. Mật Mã Cổ Xưa và Hàm Phi Euler - [Độ khó: Siêu khó]

Mô tả: Bạn là một nhà khảo cổ học và đã tìm thấy một bản đồ kho báu cổ đại. Bản đồ này được bảo vệ bởi một "mật mã phi cổ đại" dựa trên Hàm Euler's Totient (\(\phi(n)\)). Hàm \(\phi(n)\) đếm số lượng các số nguyên dương nhỏ hơn hoặc bằng n và nguyên tố cùng nhau với n. Ví dụ, \(\phi(6) = 2\) vì các số nhỏ hơn hoặc bằng 6 và nguyên tố cùng nhau với 6 là 1 và 5. Để giải mã, bạn cần tính tổng các giá trị \(\phi(i)\) cho tất cả các số i trong một đoạn [L, R] cho trước.

INPUT FORMAT

Dòng đầu tiên chứa số nguyên MaxN (\(1 \le MaxN \le 10^6\)), là giới hạn trên của các số có thể xuất hiện trong truy vấn. Dòng thứ hai chứa số nguyên Q (\(1 \le Q \le 10^5\)), là số lượng truy vấn. Q dòng tiếp theo, mỗi dòng chứa hai số nguyên L, R (\(1 \le L \le R \le MaxN\)).

OUTPUT FORMAT

Với mỗi truy vấn, in ra một số nguyên duy nhất trên một dòng, là tổng \(\sum_{i=L}^{R} \phi(i)\).

Ví dụ:

Input:

10
3
1 6
5 10
1 1

Output:

12
26
1

Giải thích:

• Giá trị của \(\phi(n)\) cho \(n=1\) đến \(10\):
  • \(\phi(1) = 1\)
  • \(\phi(2) = 1\) (các số nguyên tố cùng nhau với 2 và \(\le 2\): 1)
  • \(\phi(3) = 2\) (các số nguyên tố cùng nhau với 3 và \(\le 3\): 1, 2)
  • \(\phi(4) = 2\) (các số nguyên tố cùng nhau với 4 và \(\le 4\): 1, 3)
  • \(\phi(5) = 4\) (các số nguyên tố cùng nhau với 5 và \(\le 5\): 1, 2, 3, 4)
  • \(\phi(6) = 2\) (các số nguyên tố cùng nhau với 6 và \(\le 6\): 1, 5)
  • \(\phi(7) = 6\) (các số nguyên tố cùng nhau với 7 và \(\le 7\): 1, 2, 3, 4, 5, 6)
  • \(\phi(8) = 4\) (các số nguyên tố cùng nhau với 8 và \(\le 8\): 1, 3, 5, 7)
  • \(\phi(9) = 6\) (các số nguyên tố cùng nhau với 9 và \(\le 9\): 1, 2, 4, 5, 7, 8)
  • \(\phi(10) = 4\) (các số nguyên tố cùng nhau với 10 và \(\le 10\): 1, 3, 7, 9)
• Truy vấn 1 (1 6): Tổng \(\sum_{i=1}^{6} \phi(i) = \phi(1)+\phi(2)+\phi(3)+\phi(4)+\phi(5)+\phi(6) = 1+1+2+2+4+2 = 12\).
• Truy vấn 2 (5 10): Tổng \(\sum_{i=5}^{10} \phi(i) = \phi(5)+\phi(6)+\phi(7)+\phi(8)+\phi(9)+\phi(10) = 4+2+6+4+6+4 = 26\).
• Truy vấn 3 (1 1): Tổng \(\sum_{i=1}^{1} \phi(i) = \phi(1) = 1\).