欢迎加入2019年新生赛官方群725273468

GCD Tree

Time Limit
3s
Memory Limit
65536KB
Judge Program
Standard
Ratio(Solve/Submit)
0.00%(0/1)
Description:

Teacher Mai has a graph with n vertices numbered from 1 to n. For every edge(u,v), the weight is gcd(u,v). (gcd(u,v) means the greatest common divisor of number u and v).

You need to find a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is maximized. Print the total weight of these edges.

Input:

There are multiple test cases(about 105).

For each test case, there is only one line contains one number n(1≤n≤105).

Output:

For each test case, print the answer.

Sample Input:
1
2
3
4
5
Sample Output:
0
1
2
4
5
Source:

2015 Multi-University Training Contest 9


Submit