http://www.lydsy.com/JudgeOnline/problem.php?id=1257

k%i=k-int(k/i)*i

除法分块,对于相同的k/i用等差序列求和来做

#include<cstdio>
#include<iostream> using namespace std; int main()
{
int n,k;
scanf("%d%d",&n,&k);
long long ans=;
if(n>k)
{
ans=1ll*(n-k)*k;
n=k;
}
int l,r;
int t;
for(l=;l<=n;l=r+)
{
t=k/l; r=k/t;
if(r>n) r=n;
ans+=1ll*k*(r-l+)-1ll*(r-l+)*(l+r)/*t;
}
cout<<ans;
}

1257: [CQOI2007]余数之和sum

Time Limit: 5 Sec  Memory Limit: 162 MB
Submit: 5126  Solved: 2377
[Submit][Status][Discuss]

Description

给出正整数n和k,计算j(n, k)=k mod 1 + k mod 2 + k mod 3 + … + k mod n的值,其中k mod i表示k除以i的余数。例如j(5, 3)=3 mod 1 + 3 mod 2 + 3 mod 3 + 3 mod 4 + 3 mod 5=0+1+0+3+3=7

Input

输入仅一行,包含两个整数n, k。

Output

输出仅一行,即j(n, k)。

Sample Input

5 3

Sample Output

7

HINT

50%的数据满足:1<=n, k<=1000 100%的数据满足:1<=n ,k<=10^9

最新文章

  1. 给flash添加A链接
  2. 怎么实现CSS限制字数,超出部份显示点点点.
  3. ADHelper C#域用户操作(转)
  4. 解析C#中[],List,Array,ArrayList的区别及应用
  5. python 数字、字符串、列表常用函数
  6. js获取节点
  7. Android开发之一个未解决的bug
  8. 利用github for windows 工具将本地的内容同步到github上
  9. 搭建lamp环境
  10. Swift - 禁用UIWebView和WKWebView的下拉拖动效果
  11. My97DatePicker -- 一个功能丰富, 而且兼容 ie 6, 7的日期选择组件
  12. 卷烟厂生产管理系统基于ASP.NET
  13. 时间复杂度O()与KMP算法
  14. 安装.net 服务时出现0x80131515错误的解决办法
  15. python——vs2017安装python库时,提示pip指令问题。
  16. Hadoop2源码分析-RPC探索实战
  17. Linux中系统检测工具top命令
  18. 微信小程序 - 日期(起止)选择器组件
  19. php魔术变量
  20. openGL笔记-画基本图形

热门文章

  1. Monty Hall 问题与贝叶斯定理的理解
  2. 修改shell命令的history记录个数
  3. 【百度】大型网站的HTTPS实践(二)——HTTPS加密算法介绍
  4. [转帖]脑残式网络编程入门(二):我们在读写Socket时,究竟在读写什么?
  5. 微软自己的官网介绍 SSL 参数相关
  6. 相见恨晚的 scala - 01 [ 基础 ]
  7. 数据库优化之SQL语句优化-记录
  8. 如何杀掉Monkey测试
  9. Python 变量(下)
  10. Finding LCM LightOJ - 1215 (水题)