LightOj 1245 --- Harmonic Number (II)找规律

题目链接:http://lightoj.com/volume_showproblem.php?problem=1245

题意就是求 n/i (1<=i<=n) 的取整的和这就是到找规律的题,

i     1  2   3   4   5   6   7    8

a    8  4   2   2   1   1   1    1

你可以多写几组你会发现

有8-4个1;4-2个2;。。。其他例子也是这样;

当n = 10时

n/1 = 10, n/2 = 5说明(5, 10]这个前开后闭的区间中对应的结果都是 1 ,共有10-5 = 5个 ans += 5*1;

n/2 = 5, n/3 = 3说明(3, 5]这个前开后闭的区间中对应的结果都是 2 ,共有5-3 = 2个  ans += 2*2;

n/3 = 3, n/4 = 2说明(2, 3]这个前开后闭的区间中对应的结果都是 3 ,共有3-2 = 1个  ans += 1*3;

n/4 = 2, n/5 = 2说明(2, 2]这个前开后闭的区间中对应的结果都是 4 ,共有2-2 = 0个  ans += 0*4;

n/5 = 2, n/6 = 1说明(1, 2]这个前开后闭的区间中对应的结果都是 5 ,共有2-1 = 1个  ans += 1*5;

对于一个比较大的数n,直接循环一定会错,所以要优化,对于 1 - (int)sqrt(n)所对应的另一半即[n/(int)sqrt(n), n/1]这些数一定只出现了一次,所以加上,剩下的那些就是出现多次的了,按照规律进行处理,注意会加多的那个部分;

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<algorithm>
#include<math.h>
using namespace std;
#define N 20100 int main()
{
int T, n,t=;
scanf("%d", &T);
while(T--)
{
scanf("%d", &n);
int i=, cnt=;
long long ans=;
if(n==)
{
printf("Case %d: 1\n", t++);
continue;
}
while()
{
int a=n/i;
int b=n/(i+);
ans=ans+a+(a-b)*i;///结果;
cnt=cnt+(a-b)+;///表示已经加了几个数了;
i++;
if(cnt==n-)///当还剩一个数时就结束就行了,并且还要把这个数加上;
{
ans+=n/i;
break;
}
if(b<=i)///当后面那个数<=i事就说明已经加完了;
break;
}
printf("Case %d: %lld\n", t++, ans);
}
return ;
}

简单的写法

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <vector>
#include <math.h>
using namespace std;
typedef long long LL;
const int oo = 0xfffffff;
const int N = 1e7+;
const double eps = 1e-; int main()
{
int T, t = ; scanf("%d", &T); while(T--)
{
LL n; scanf("%lld", &n); LL ans = , a = , b = , k = (int)sqrt(n); for(int i=; i<=k; i++)
{
a = n/i, b = n/(i+);
ans += a + (a-b)*i;
}
if(k == n/k)
ans -= k;
printf("Case %d: %lld\n", t++, ans);
}
return ;
}
上一篇:iOS 设置状态栏的背景颜色


下一篇:Java中数组的插入,删除,扩张