f(n)

Time Limit: 1000ms
Memory Limit: 32768KB
This problem will be judged on HDU. Original ID: 2582
64-bit integer IO format: %I64d      Java class name: Main

Description

This time I need you to calculate the f(n) . (3<=n<=1000000)

f(n)= Gcd(3)+Gcd(4)+…+Gcd(i)+…+Gcd(n).
Gcd(n)=gcd(C[n][1],C[n][2],……,C[n][n-1])
C[n][k] means the number of way to choose k things from n some things.
gcd(a,b) means the greatest common divisor of a and b.

Input

There are several test case. For each test case:One integer n(3<=n<=1000000). The end of the in put file is EOF.

Output

For each test case:
The output consists of one line with one integer f(n).

Sample Input

3
26983

Sample Output

3
37556486

Source

Language: 
Theme: 
Share Code? 

Powered by NB231 | Current Style: .