题目大意:对下列代码进行优化
long long H( int n ) {
long long res = 0;
for( int i = 1; i <= n; i++ )
res = res + n / i;
return res;
}
题目思路:为了避免超时,要想办法进行优化
以9为例:
9/1 = 9
9/2 = 4
9/3 = 3
9/4 = 2
9/5 = 1
9/6 = 1
9/7 = 1
9/8 = 1
9/9 = 1
拿1来看,同为1的区间长度为:9/(9/5)+1-5,
得出通式:值相同的区间长度为:n/(n/i)+1-i。
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<iostream>
#include<algorithm>
#define INF 0x3f3f3f3f
#define MAXSIZE 1000005
#define LL long long using namespace std; int main()
{
int T,cns=;
LL n;
scanf("%d",&T);
while(T--)
{
scanf("%lld",&n);
LL i=;
LL ans=;
while(i<=n)
{
ans=ans+(n/(n/i)-i+)*(n/i);
i=n/(n/i)+;
}
printf("Case %d: %lld\n",cns++,ans);
}
return ;
}