题目描述
Once Qi Ge met a problem, he wrote a code like this:
__int64 Gao(int n){
__int64 cnt=0;
for(int i=1;i<=n;i++)
cnt=cnt+n/i;
return cnt;
}
but he made a mistake that he used the integer divisions. So you are given n, your task is to calculate the answer of Gao(n).
输入
The input contains several test cases. Input starts with a integer T (T<=1000), following T test cases.
Each test case starts with a n (1<=n<2^31).
输出
For each case, print the case number first, then print your answer of Gao(n).
Case 1: 1
Case 2: 3
Case 3: 5
Case 4: 8
Case 5: 10
Case 6: 46475828386
提示
Notice about the complexity of your algorithm. The input of n is very large, so you must improve your algorithm.