--数论-被想复杂的一道题

计算 n/1 + n/2 + n/3 +ｎ/4 + ... + n/n =?

 

一开始的思路是将n提取出来 ：

 

原式 = n* （1+ 1/2 + 1/3 + 1/4 + ... 1/n)  = n * (ln(n) + c) c是欧拉常数 ，约为0.5772,样例挂

然后发现这样会多加上那些没被整除的被省略的分数，比如 2/3 = 0，但是在上面的式子里分数也是算上的，再次去bug,找出多加的数就行了

没实现。。。

从网上一看，远没有那么难！

然后自己敲过了：

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int main(){
long long t,n;
scanf("%lld",&t);
while(t--){
scanf("%lld",&n);
long long  s = 0 ;
long long id;
for(long long i = 1;i<= n;){
id = n/i;
s += id;
if(n/id == id)i++;
else{
s+=(n/id - i)*id;
i = n/id + 1;
}
}
printf("%lld\n",s);
}
}