[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<stdio.h>
#include<math.h>
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<stdio.h>
#include<math.h>
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
