Harmonic Number (II)

Description

I was trying to solve problem '1234 - Harmonic Number', I wrote the following code

long long H( int n ) {
    long long res = 0;
    for( int i = 1; i <= n; i++ )
        res = res + n / i;
    return res;
}

Yes, my error was that I was using the integer divisions only. However, you are given n, you have to find H(n) as in my code.

Input

Input starts with an integer T (≤ 1000), denoting the number of test cases.

Each case starts with a line containing an integer n (1 ≤ n < 231).

Output

For each case, print the case number and H(n) calculated by the code.

Sample Input

11

1

2

3

4

5

6

7

8

9

10

2147483647

Sample Output

Case 1: 1

Case 2: 3

Case 3: 5

Case 4: 8

Case 5: 10

Case 6: 14

Case 7: 16

Case 8: 20

Case 9: 23

Case 10: 27

Case 11: 46475828386

思路:类似分块的思想最多有2sqrt(n)个数;

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define esp 0.00000000001
#define pi 4*atan(1)
const int N=1e3+,M=1e7+,inf=1e9+,mod=1e9+;
int main()
{
int T,cas=;
scanf("%d",&T);
while(T--)
{
ll x;
scanf("%lld",&x);
ll ans=;
for(ll i=;i*i<=x;i++)
{
if(i!=x/i)
ans+=x/i;
ll len=(x/i)-x/(i+);
ans+=i*len;
}
printf("Case %d: %lld\n",cas++,ans);
}
return ;
}

最新文章

  1. Log4j快速使用精简版
  2. JavaBean学习总结(上)
  3. WPF 将DLL嵌入EXE文件(安装包)
  4. Linux网络共享管理(ssh,nfs,samba)
  5. C#在使用串口读一长段数据时,前面加延时,等串口缓冲全部收到再去读
  6. BootStrap -- Grid System
  7. SVG基础以及使用Javascript DOM操作SVG
  8. CentOS x 64 MooseFS 学习
  9. linux环境安装mysql,以及mysql基本的终端操作命令
  10. python输出彩色字体
  11. having使用
  12. myeclipse cannot connect to vm
  13. Github的一般用法
  14. js数组之从数组中删除元素
  15. (线段树)Just a Hook -- hdu -- 1689
  16. Workstation和Virtualbox的虚拟机磁盘扩容方式.
  17. 洛谷 P4091 [HEOI2016/TJOI2016]求和 解题报告
  18. CSS 块级元素、内联元素概念
  19. [转]AngularJS 实现 Table的一些操作(示例大于实际)
  20. Jmeter获取当前时间、历史时间、未来时间的方式

热门文章

  1. SonarQube 平台搭建
  2. 【BZOJ1266】[AHOI2006]上学路线route Floyd+最小割
  3. 《从零开始学Swift》学习笔记(Day 45)——重写方法
  4. LIS(模板)
  5. EasyNVR摄像机无插件直播按需RTSP拉流播放流程详解
  6. 【转】再谈CLR查找和加载程序集的方式
  7. 微信小程序开发遇见的问题之一
  8. Java 注解入门
  9. Python Selenium 自动化测试
  10. shutil 模块 高级的文件、文件夹、压缩包 处理模块