ZOJ3175 Number of Containers[数学题]

Number of Containers

Time Limit: 1 Second Memory Limit: 32768 KB

For two integers m and k, k is said to be a container of m if k is divisible by m. Given 2 positive integers n and m (m < n), the function f(n, m) is defined to be the number of containers of m which are also no greater than n. For example, f(5, 1)=4, f(8, 2)=3, f(7, 3)=1, f(5, 4)=0...

Let us define another function F(n) by the following equation:

Now given a positive integer n, you are supposed to calculate the value of F(n).

Input

There are multiple test cases. The first line of input contains an integer T(T<=200) indicating the number of test cases. Then T test cases follow.

Each test case contains a positive integer n (0 < n <= 2000000000) in a single line.

Output

For each test case, output the result F(n) in a single line.

Sample Input

2
1
4

Sample Output

0
4

题目就是要我们求:n*(1/1+1/2+1/3+……1/(n-2)+1/(n-1))-n
由于题目的数据太大，显然暴力是会tle，于是建立如上的图，发现：
x*y=n这条直线是关于y=x对称，于是
1+2+1就是结果了。
能想到根号n就几乎是知道答案了。


code:

 1 #include<stdio.h>
 2 #include<math.h>
 3 
 4 int main()
 5 {
 6     int t;
 7     scanf("%d",&t);
 8     int n;
 9     while(t--)
10     {
11         int i;
12         int t;
13         long long sum=0;
14         scanf("%d",&n);
15         t=(int)(sqrt(n)+0.000001);
16         for(i=1;i<=t;i++)
17             sum+=(n/i);
18         sum*=2;
19         sum=sum-t*t-n;
20         printf("%lld\n",sum);
21     }
22     return 0;
23 }