P2261 [CQOI2007]余数求和
关键在于化简公式,题目所求$\sum_{i=1}^{n}k\mod i$
简化式子,也就是$\sum_{i=1}^{n}(k-\frac{k}{i}\times k)$
$=n*k-\sum_{i=1}^{n}\frac{k}{i}\times k$
$⌊ \frac{m}{k}⌋$ 共有 $O( √ m)$ 种取值,直接计算。总时间复杂度 $O( √ m)$
观察下图:
你会发现$\frac{k}{i}$是有规律的,或者说相同的紧挨着,分布在同一个块中
确定$\frac{k}{i}$取值相同的区间$[l,r]$,$r=min(n,k/(k/l))$
$k/l$代表这一部分的取值,$k/(k/l)$就是区间的右端点
确定了区间,那么根据等差数列求和公式$\frac{(S1+Sn)\times n}{2}$
#include<bits/stdc++.h> #define LL long long
using namespace std; LL n,k; int main()
{
scanf("%lld%lld",&n,&k);
LL ans=n*k;
for(LL l=,r;l<=n;l=r+){
if(k/l!=) r=min(k/(k/l),n);
else r=n;
ans-=(k/l)*(r-l+)*(l+r)/;
} printf("%lld\n",ans); return ;
}
洛谷——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]余数求和
洛谷题目链接:[CQOI2007]余数求和 题目背景 数学题,无背景 题目描述 给出正整数n和k,计算G(n, k)=k mod 1 + k mod 2 + k mod 3 + - + k mod n ...
-
洛谷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 $ $$ ...
随机推荐
-
scikit-learn一般实例之六:构建评估器之前进行缺失值填充
本例将会展示对确实值进行填充能比简单的对样例中缺失值进行简单的丢弃能获得更好的结果.填充不一定能提升预测精度,所以请通过交叉验证进行检验.有时删除有缺失值的记录或使用标记符号会更有效. 缺失值可以被替 ...
-
【安装mysql数据库】
方法/步骤 请注意上图中选择Custom选项,这样才能修改安装目录. 请注意为了数据安全,不要把mysql安装在系统盘,如C:盘. 可以在其他盘符下,新建两个文件夹,一个存储mysql的文件, ...
-
Intel pin 2.14/CentOS 6 X86-64/安装
环境:Intel Pin 2.14 CentOS 6 X86-64 --linux.tar.gz 进入 ./source/tools/ManualExamples make all TARGET=in ...
-
20145208 实验四 Android开发基础
20145208 实验四 Android开发基础 安装Android Studio 安装的具体步骤在老师的链接中已经很详细了,在此就不做赘述了. 在此提出我觉得安装的时候需要注意的两个地方 一是安装地 ...
-
JavaScript------入门
index.jsp <%@ page language="java" import="java.util.*" pageEncoding="gb ...
-
jade复用
jade复用说白了就是模板的继承. 使用 block 标识符,设置一个可修改的代码片段 layout.jade doctype html html head block title title Def ...
-
binary-tree-maximum-path-sum(mock)
注意: // 注意,如果一个类放在另一个类里面,初始化时候会报错 Solution is not a enclosing class// 这是因为如果TreeNode不是static,那么要求先有外部 ...
-
[置顶] Vim用正则表达式进行批量修改
vim可以设置 magic 这个东西, magic就是设置哪些元字符要加反斜杠哪些不用加的. 简单来说: magic(\m):除了 $ . * ^ 之外其他元字符都要加反斜杠. nomagic(\M) ...
-
nginx 源码安装
安装环境: 操作系统:Ubuntu 12.04 Nginx: V1.4.2 PCRE: V8.33 zlib: V1.2.8 下载上述源包到当前用户主目录(本机:/hom ...
-
KVC该机制
KVC该机制 KVC是cocoa的大招,用来间接获取或者改动对象属性的方式. 一.KVC的作用: KVC大招之中的一个: [self setValuesForKeysWithDictionary:di ...