题目链接:Harmonic Number (II)
题意计算n/i的和,i从1到n
题解:如果暴力一定会超时 ,可以先选择打表找规律
通过打表可以得到以下规律:
那么最后的和为2前面的和减去根号n根号n
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
using namespace std;
int main()
{
int t;
int i,l=1;
scanf("%d",&t);
while(t--)
{
long long n,sum=0;
scanf("%lld",&n);
int i;
long long p=sqrt(n);
for(i=1;i<=p;i++)
{
sum+=n/i;
}
printf("Case %d: %lld\n",l++,2*sum-p*p);
}
}