zoj 3175 Number of Containers （nbut1375）计算n /1+n/2+n/3+n/4....+n/n

[1375] Guess The Number
时间限制: 1000 ms　内存限制: 65535 K

问题描述
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).

输入
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.
输出
For each test case, output the result F(n) in a single line.
样例输入
2
1
4
样例输出
0
4
提示
无来源
ZOJ 3175 Number of Containers

题意：

求n*(1/1+1/2+1/3+……1/(n-2)+1/(n-1))-n
的值

由于n非常大所以不能直接暴力

画图可以用横坐标表示i 从改点画一条垂直的线这条线上的所有整数点的个数就是 n/i

那么n/1+n/2+n/3+……n/(n-2)+n/(n-1)+n/n 可以表示为i*(n/i)=n这条线

答案就是这条线与坐标轴围成的面积内的整数点的个数

画一条x=y的线与x*y=n相交可以知道面积关于x=y对称

我们求n/1+n/2+n/3+…… 只求到k=sqrt(n)处（1个梯形）之后乘以2 （得到2个梯形的面积其中有一个正方形的区域是重复的）减去重复的区域k*k个即可

[cpp]
#include
#include

int main()
{
int t;
scanf("%d",&t);
int n;
while(t--)
{
int i;
int t;
long long sum=0;
scanf("%d",&n);
t=(int)sqrt((double)n);
for(i=1;i<=t;i++)
sum+=(n/i);
sum*=2;
sum=sum-t*t-n;
printf("%lld\n",sum);
}
return 0;
}

#include
#include

int main()
{
int t;
scanf("%d",&t);
int n;
while(t--)
{
int i;
int t;
long long sum=0;
scanf("%d",&n);
t=(int)sqrt((double)n);
for(i=1;i<=t;i++)
sum+=(n/i);
sum*=2;
sum=sum-t*t-n;
printf("%lld\n",sum);
}
return 0;
}
此外我们可以用这种方法快速求n/1+n/2+n/3+......n/n

zoj 3175 Number of Containers （nbut1375） 计算n /1+n/2+n/3+n/4....+n/n