Tổng các ước chung lớn nhất

Xem dạng PDF

Gửi bài giải


Điểm: 0,56 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 512M
Input: stdin
Output: stdout

Nguồn bài:
ACM World Final Warm up 1 - 2008
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Một lần, ktuan được thầy giáo cho bài tập về nhà, yêu cầu tính tổng tất cả các ước chung lớn nhất của các cặp số ~(i~, ~j)~ thỏa mãn: ~1 \le~ i ~< j \le N~ ~(N~ là một số tự nhiên cho trước). Rất nhanh chóng, ktuan đã cho ra một đoạn code như sau:

for i := 1 to N - 1 do
    for j := i + 1 to N do
        sum := sum + gcd(i, j);

với gcd là hàm tính ước chung lớn nhất của ~2~ số, sum chính là kết quả cuối cùng. Thầy giáo yêu cầu ktuan dùng chương trình trên để tính kết quả với ~N = 1000000~. Tuy nhiên, chương trình trên chạy quá lâu. Để khắc phục vấn đề, ktuan đã viết lại đoạn mã đó bằng ~C + +~ (với hi vọng ~C + +~ sẽ chạy nhanh hơn pascal nhiều):

for(int i = 1; i < N; ++ i)
    for(int j = i + 1; j <= N; ++ j)
        sum += gcd(i, j);

Thật không may, đoạn chương trình trên vẫn không giải quyết được vấn đề, bạn hãy giúp ktuan giải đáp yêu cầu của thầy giáo.

Lưu ý: bài này có thể giải bằng phương pháp Quy hoạch động và các kiến thức sơ đẳng trong toán học, không cần sử dụng những kiến thức toán học phức tạp không nằm trong phạm vi chương trình phổ thông.

Input

  • Gồm nhiều dòng, mỗi dòng là một số ~N~ ~(1 \le N \le 10^{6})~ ứng với một test.
  • Dữ liệu vào sẽ kết thúc sau khi gặp ~N = 0~ (bạn không cần thực hiện test này).

Output

  • Với mỗi giá trị của ~N~, in ra một dòng là giá trị của sum sau khi thực hiện đoạn mã trên.

Sample Input

4
0

Sample Output

7

Bình luận

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



  • -1
    tboros2  đã bình luận lúc 3, Tháng 8, 2023, 1:24

    bài này cụ thể dựa trên đánh giá: với g=gcd(i,j) (i thuộc [1;j-1]) thì tồn tại phi(j/g) giá trị i thỏa mãn. Với phi là phi hàm euler.

    Còn cách cài thì tương tự như cách cài sàng eratosthenes cho cả phi lẫn kết quả


  • 0
    dungxa3k26  đã bình luận lúc 24, Tháng 10, 2022, 9:03

    xinnn solution với ạ, pls :_(


    • 3
      tboros2  đã bình luận lúc 2, Tháng 8, 2023, 7:27

      https://www.geeksforgeeks.org/summation-gcd-pairs-n/