先举个例子,假如给你的数是100的话,将100/2=50;是不是就是100除100-51之间的数取整为1;
100/3=33;100除50到34之间的数为2,那么这样下去到sqrt(100);就可以求得100除以sqrt(100)+1到100之间数的和,也就是后90项的和以求得。
剩余的前10项直接代公式求就行了。
复杂度为2*sqrt(N);
http://lightoj.com/volume_showproblem.php?problem=1245
1 #include<stdio.h>
2 #include<algorithm>
3 #include<iostream>
4 #include<stdlib.h>
5 #include<string.h>
6 #include<math.h>
7 typedef long long ll;
8 using namespace std;
9 int main(void)
10 {
11 ll i,j,k,p,q,n;
12 scanf("%lld",&n);
13 for(i=1; i<=n; i++)
14 {
15 scanf("%lld",&p);
16 ll x=0;ll tt=0;
17 k=p;
18 for(j=2;j<=sqrt(p);j++)
19 {
20 x+=(k-(p/j))*(j-1);
21 k=p/j;
22 }
23 for(j=k;j>=1;j--)
24 {
25 x+=p/j;
26 }
27 printf("Case %lld: ",i);
28 printf("%lld\n",x);
29 }
30 }