UVa 11526 - H(n)

ACM对抗赛决赛题,在比赛时没出,后来找学长给讲了,利用相同值一起加减少运算次数,就过了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<iostream>
using namespace std;
long long H(long long n){
long long res=0,cur,last=n;
for(long long i=1;i<=n;i++){
cur=n/i;
res+=cur;
if(cur<last){
res+=(n/cur-i)*cur;
i=n/cur;
last=cur;
}
}
return res;
}
int main(){
int t;
cin>>t;
while(t--){
long long n;
cin>>n;
cout<<H(n)<<endl;
}
return 0;
}

** 本文迁移自我的CSDN博客,格式可能有所偏差。 **