博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
AcWing 199. 余数之和 (除法分块)打卡
阅读量:5083 次
发布时间:2019-06-13

本文共 819 字,大约阅读时间需要 2 分钟。

给出正整数n和k,计算j(n, k)=k mod 1 + k mod 2 + k mod 3 + … + k mod n的值。

例如j(5, 3)=3 mod 1 + 3 mod 2 + 3 mod 3 + 3 mod 4 + 3 mod 5=0+1+0+3+3=7。

输入格式

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

输出格式

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

数据范围

1n,k1091≤n,k≤109

输入样例:

5 3

输出样例:

7 题意:求题目所给的等式 思路:直接O(n)遍历肯定不行,我们尝试优化,首先我们  n%p = n - n/p*p   我们就可以把原式变成 n*p - 累加(1-m) n/i*i; 然后再利用除法分块原理能知道一段区间的除法值是一样的,然后用等差数列求和,然后得出值  除法分块: begin=i; end=n/(n/i); 首先n/i是被除后的值,然后我要最大的除值的最大下标位置,肯定是拿总和除以值就得出下标位置所在
#include
#define maxn 200005#define mod 1000000007using namespace std;typedef long long ll;ll n,m;int main(){ cin>>m>>n; ll x=n*m; ll sum=0; if(m>=n){ m=n; } for(int i=1;i<=m;i=n/(n/i)+1){ ll q=n/(n/i); q=min(q,m); ll z=(i+q)*(q-i+1)/2; sum+=z*(n/i); } cout<

 

 

转载于:https://www.cnblogs.com/Lis-/p/11000920.html

你可能感兴趣的文章
一天一道算法题--5.30---递归
查看>>
JS取得绝对路径
查看>>
排球积分程序(三)——模型类的设计
查看>>
python numpy sum函数用法
查看>>
php变量什么情况下加大括号{}
查看>>
linux程序设计---序
查看>>
【字符串入门专题1】hdu3613 【一个悲伤的exkmp】
查看>>
C# Linq获取两个List或数组的差集交集
查看>>
HDU 4635 Strongly connected
查看>>
ASP.NET/C#获取文章中图片的地址
查看>>
Spring MVC 入门(二)
查看>>
格式化输出数字和时间
查看>>
页面中公用的全选按钮,单选按钮组件的编写
查看>>
java笔记--用ThreadLocal管理线程,Callable<V>接口实现有返回值的线程
查看>>
BZOJ 1047 HAOI2007 理想的正方形 单调队列
查看>>
各种语言推断是否是手机设备
查看>>
这个看起来有点简单!--------实验吧
查看>>
PHP count down
查看>>
JVM参数调优:Eclipse启动实践
查看>>
(旧笔记搬家)struts.xml中单独页面跳转的配置
查看>>