[洛谷P2261] [CQOI2007]余数求和

时间:2022-09-04 10:35:13

洛谷题目链接:[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\)都一样该怎么办呢?我们来看一张图(竖线是块与块的分界线):

[洛谷P2261] [CQOI2007]余数求和

其实我们可以将原来的一个块再拆成几个块再计算.

既然知道了这个方法,我们就可以继续化简式子了.

\[ans=\sum_{i=1}^{n}k\mod i
\]

\[ans=\sum_{i=1}^{n}k-\lfloor \frac{k}{i}\rfloor \times i
\]

根据我们分的块,在同一个块内的\(\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]余数求和的更多相关文章

  1. 洛谷 P2261 &lbrack;CQOI2007&rsqb;余数求和 解题报告

    P2261 [CQOI2007]余数求和 题意: 求\(G(n,k)=\sum_{i=1}^n k \ mod \ i\) 数据范围: \(1 \le n,k \le 10^9\) \(G(n,k)\ ...

  2. 洛谷——P2261 &lbrack;CQOI2007&rsqb;余数求和

    P2261 [CQOI2007]余数求和 关键在于化简公式,题目所求$\sum_{i=1}^{n}k\mod i$ 简化式子,也就是$\sum_{i=1}^{n}(k-\frac{k}{i}\time ...

  3. 洛谷P2261 &lbrack;CQOI2007&rsqb; 余数求和 &lbrack;数论分块&rsqb;

    题目传送门 余数求和 题目背景 数学题,无背景 题目描述 给出正整数n和k,计算G(n, k)=k mod 1 + k mod 2 + k mod 3 + … + k mod n的值,其中k mod ...

  4. 洛谷 P2261 &lbrack;CQOI2007&rsqb;余数求和

    洛谷 一看就知道是一个数学题.嘿嘿- 讲讲各种分的做法吧. 30分做法:不知道,这大概是这题的难点吧! 60分做法: 一是直接暴力,看下代码吧- #include <bits/stdc++.h& ...

  5. 洛谷 P2261 &lbrack;CQOI2007&rsqb;余数求和 &vert;&vert;整除&lpar;数论&rpar;分块

    参考:题解 令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 ...

  6. 【洛谷P2261】余数求和

    题目大意:给定 n, k,求\(\sum\limits_{i=1}^n k\%n\) 的值. 题解:除法分块思想的应用. \(x\%y=x-y\lfloor {x\over y}\rfloor\),因 ...

  7. 洛谷 2261 &lbrack;CQOI2007&rsqb;余数求和

    题目戳这里 一句话题意 求 \(\sum_{i=1}^{n} (k ~~\texttt{mod} ~~i)\) Solution 30分做法: 说实话并不知道怎么办. 60分做法: 很明显直接一遍o( ...

  8. &lbrack;Luogu P2261&rsqb; &lbrack;CQOI2007&rsqb;余数求和 &lpar;取模计算&rpar;

    题面 传送门:https://www.luogu.org/problemnew/show/P2261 Solution 这题显然有一个O(n)的直接计算法,60分到手. 接下来我们就可以拿出草稿纸推一 ...

  9. P2261 &lbrack;CQOI2007&rsqb;余数求和 【整除分块】

    一.题面 P2261 [CQOI2007]余数求和 二.分析 参考文章:click here 对于整除分块,最重要的是弄清楚怎样求的分得的每个块的范围. 假设$ n = 10 ,k = 5 $ $$  ...

随机推荐

  1. 聊天室(Java实现)

    功能: 登录 若用户账号不存在,弹出错误 若用户密码错误,弹出错误 若用户账号已在线,弹出错误 注册 若用户已注册,弹出错误 聊天室 多人聊天,类似QQ里的群. 点击右侧的在线用户,可进行一对一聊天. ...

  2. IE9 打不开界面也不报错,只有打开控制台才会显示 - console

    IE9下,打开界面不报错也不展示数据,打开控制台时就能加载出数据,有可能是代码中有console

  3. Nginx配置单主机多域名

    http { include mime.types; default_type application/octet-stream; sendfile on; keepalive_timeout 65; ...

  4. android studio对于错误拼写&sol;不识别的英文单词,给予波浪提示

    使用自己的名字当Tag.却发现有个非常不用好的提示.波浪,我浪个你妹. Typo:In word ‘miyuehu’ less...(Ctrl+F1) spellchecker inspection ...

  5. Redis必须注意的慢查询问题

    今天解析服务在查询Redis的Set数据过程中抛出timeout exception,产生异常的方法是: db.SetMembers(key); 这个API返回结果是指定set内的所有kv对象: 解决 ...

  6. http&colon;&sol;&sol;blog&period;csdn&period;net&sol;woshiyjk&sol;article&sol;details&sol;7895888

    http://blog.csdn.net/woshiyjk/article/details/7895888

  7. canvas基础2--绘制图形

    栅格 绘制矩形 不同于SVG,HTML中的元素canvas只支持一种原生的图形绘制:矩形.所有其他的图形的绘制都至少需要生成一条路径.不过,我们拥有众多路径生成的方法让复杂图形的绘制成为了可能. 首先 ...

  8. Java连接各类数据库

    几种常用数据库的连接,以及Dao层的实现. 1.加载JDBC驱动: 1 加载JDBC驱动,并将其注册到DriverManager中: 2 //MySQL数据库 3 Class.forName(&quo ...

  9. 40&period; Testing Prev &Tab;Part IV&period; Spring Boot features

    40. Testing Spring Boot provides a number of utilities and annotations to help when testing your app ...

  10. Linux入门&lpar;二&rpar;Linux基本命令及基本操作

    1 常用Linux命令 图形界面进入到字符界面: ctrl+alt+F2~F6 字符界面进入到图形界面:ctrl +alt+F7 查看本机ip:  ifconfig  (windows是:ipconf ...