首页 > 代码库 > LightOJ - 1245 Harmonic Number (II) 求同值区间的和
LightOJ - 1245 Harmonic Number (II) 求同值区间的和
题目大意:对下列代码进行优化
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=1; LL n; scanf("%d",&T); while(T--) { scanf("%lld",&n); LL i=1; LL ans=0; while(i<=n) { ans=ans+(n/(n/i)-i+1)*(n/i); i=n/(n/i)+1; } printf("Case %d: %lld\n",cns++,ans); } return 0; }
LightOJ - 1245 Harmonic Number (II) 求同值区间的和
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。