洛谷题目链接:[CQOI2007]余数求和
题目背景
数学题,无背景
题目描述
给出正整数n和k,计算G(n, k)=k mod 1 + k mod 2 + k mod 3 + … + k mod n的值,其中k mod i表示k除以i的余数。例如G(10, 5)=5 mod 1 + 5 mod 2 + 5 mod 3 + 5 mod 4 + 5 mod 5 …… + 5 mod 10=0+1+2+1+0+5+5+5+5+5=29
输入输出格式
输入格式:
两个整数n k
输出格式:
答案
输入输出样例
输入样例#1:
10 5
输出样例#1:
29
说明
30%: n,k <= 1000
60%: n,k <= 10^6
100% n,k <= 10^9
一句话题意: 给出\(n,k(n,k<=10^9)\),求$$\sum_{i=1}^{n}k\mod i$$
题解: 学习这个之前我们首先需要知道什么是整除分块.
那么对于一个块内,所有的\(\lfloor \frac n i \rfloor\)都是一样的.但是如果我还想让一个块内所有的\(\lfloor \frac n i \rfloor\)都一样该怎么办呢?我们来看一张图(竖线是块与块的分界线):
其实我们可以将原来的一个块再拆成几个块再计算.
既然知道了这个方法,我们就可以继续化简式子了.
\]
\]
根据我们分的块,在同一个块内的\(\lfloor \frac{k}{i}\rfloor\)和\(\lfloor \frac{n}{i}\rfloor\)是一样的,所以这个块内的答案也就可以用\((r-l+1) \times (k \mod l+k \mod r)/2\)表示,然后再判断下一个区间的位置就可以了.
很好想的,代码也很好理解,如果不懂可以看代码再理解一下.
#include<bits/stdc++.h>
using namespace std;
typedef int _int;
#define int long long
int n, k, ans = 0;
_int main(){
cin >> n >> k;
int l = 1, rn, rk, lim = min(n, k);
while(l <= lim){
rn = n/(n/l), rk = k/(k/l);
if(rn < rk) ans += (rn-l+1)*(k%l+k%rn)/2, l = rn+1;
else ans += (rk-l+1)*(k%l+k%rk)/2, l = rk+1;
}
if(lim == k) ans += (n-k)*k;
cout << ans << endl;
return 0;
}
[洛谷P2261] [CQOI2007]余数求和的更多相关文章
-
洛谷 P2261 [CQOI2007]余数求和 解题报告
P2261 [CQOI2007]余数求和 题意: 求\(G(n,k)=\sum_{i=1}^n k \ mod \ i\) 数据范围: \(1 \le n,k \le 10^9\) \(G(n,k)\ ...
-
洛谷——P2261 [CQOI2007]余数求和
P2261 [CQOI2007]余数求和 关键在于化简公式,题目所求$\sum_{i=1}^{n}k\mod i$ 简化式子,也就是$\sum_{i=1}^{n}(k-\frac{k}{i}\time ...
-
洛谷P2261 [CQOI2007] 余数求和 [数论分块]
题目传送门 余数求和 题目背景 数学题,无背景 题目描述 给出正整数n和k,计算G(n, k)=k mod 1 + k mod 2 + k mod 3 + … + k mod n的值,其中k mod ...
-
洛谷 P2261 [CQOI2007]余数求和
洛谷 一看就知道是一个数学题.嘿嘿- 讲讲各种分的做法吧. 30分做法:不知道,这大概是这题的难点吧! 60分做法: 一是直接暴力,看下代码吧- #include <bits/stdc++.h& ...
-
洛谷 P2261 [CQOI2007]余数求和 ||整除(数论)分块
参考:题解 令f(i)=k%i,[p]表示不大于p的最大整数f(i)=k%i=k-[k/i]*i令q=[k/i]f(i)=k-qi如果k/(i+1)=k/i=qf(i+1)=k-q(i+1)=k-qi ...
-
【洛谷P2261】余数求和
题目大意:给定 n, k,求\(\sum\limits_{i=1}^n k\%n\) 的值. 题解:除法分块思想的应用. \(x\%y=x-y\lfloor {x\over y}\rfloor\),因 ...
-
洛谷 2261 [CQOI2007]余数求和
题目戳这里 一句话题意 求 \(\sum_{i=1}^{n} (k ~~\texttt{mod} ~~i)\) Solution 30分做法: 说实话并不知道怎么办. 60分做法: 很明显直接一遍o( ...
-
[Luogu P2261] [CQOI2007]余数求和 (取模计算)
题面 传送门:https://www.luogu.org/problemnew/show/P2261 Solution 这题显然有一个O(n)的直接计算法,60分到手. 接下来我们就可以拿出草稿纸推一 ...
-
P2261 [CQOI2007]余数求和 【整除分块】
一.题面 P2261 [CQOI2007]余数求和 二.分析 参考文章:click here 对于整除分块,最重要的是弄清楚怎样求的分得的每个块的范围. 假设$ n = 10 ,k = 5 $ $$ ...
随机推荐
-
聊天室(Java实现)
功能: 登录 若用户账号不存在,弹出错误 若用户密码错误,弹出错误 若用户账号已在线,弹出错误 注册 若用户已注册,弹出错误 聊天室 多人聊天,类似QQ里的群. 点击右侧的在线用户,可进行一对一聊天. ...
-
IE9 打不开界面也不报错,只有打开控制台才会显示 - console
IE9下,打开界面不报错也不展示数据,打开控制台时就能加载出数据,有可能是代码中有console
-
Nginx配置单主机多域名
http { include mime.types; default_type application/octet-stream; sendfile on; keepalive_timeout 65; ...
-
android studio对于错误拼写/不识别的英文单词,给予波浪提示
使用自己的名字当Tag.却发现有个非常不用好的提示.波浪,我浪个你妹. Typo:In word ‘miyuehu’ less...(Ctrl+F1) spellchecker inspection ...
-
Redis必须注意的慢查询问题
今天解析服务在查询Redis的Set数据过程中抛出timeout exception,产生异常的方法是: db.SetMembers(key); 这个API返回结果是指定set内的所有kv对象: 解决 ...
-
http://blog.csdn.net/woshiyjk/article/details/7895888
http://blog.csdn.net/woshiyjk/article/details/7895888
-
canvas基础2--绘制图形
栅格 绘制矩形 不同于SVG,HTML中的元素canvas只支持一种原生的图形绘制:矩形.所有其他的图形的绘制都至少需要生成一条路径.不过,我们拥有众多路径生成的方法让复杂图形的绘制成为了可能. 首先 ...
-
Java连接各类数据库
几种常用数据库的连接,以及Dao层的实现. 1.加载JDBC驱动: 1 加载JDBC驱动,并将其注册到DriverManager中: 2 //MySQL数据库 3 Class.forName(&quo ...
-
40. Testing Prev 	Part IV. Spring Boot features
40. Testing Spring Boot provides a number of utilities and annotations to help when testing your app ...
-
Linux入门(二)Linux基本命令及基本操作
1 常用Linux命令 图形界面进入到字符界面: ctrl+alt+F2~F6 字符界面进入到图形界面:ctrl +alt+F7 查看本机ip: ifconfig (windows是:ipconf ...