Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

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

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/gcdsum


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<=i< j<=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<=N<=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.

Example

Input:
4
0

Output:
7

Được gửi lên bởi:VOJ problem setters
Ngày:2008-03-15
Thời gian chạy:1s
Giới hạn mã nguồn:10000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:ACM World Final Warm up 1 - 2008

hide comments
2020-01-21 07:07:49
Chứng minh được F(N) = tổng [1..N]GCD(1, N) là hàm nhân tính.
2017-07-21 20:51:54
code 3 4 dong :D
2017-06-21 14:25:12
:)

Last edit: 2017-06-21 14:27:42
2017-06-14 05:37:28
ai đấm AC cho e xin ý tưởng đi ạ
10^6 quá lớn
2011-01-27 07:28:12 Thỏ con làm bánh
Trời ơi, thực hiện khoảng 6 triệu phép tính mà cũng TLE sao >.<
2009-04-11 07:44:39 dhkhtn
Vai test khac : http://icpcres.ecs.baylor.edu/onlinejudge/external/114/11424.html
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.