题面
传送门:https://www.luogu.org/problemnew/show/P2261
Solution
这题显然有一个O(n)的直接计算法,60分到手。
接下来我们就可以拿出草稿纸推一推式子了
首先,取模运算在这里很不和谐,我们得转换一下。
对于任意取模计算,我们都有:
所以,我们可以做以下推算
经过一些手算,我们发现k/i(向下取整)是由一段一段的区间组成的,如下图
显然,每段区间的右端点可以通过二分的方法来找
对于每一段区间,我们可以把k/i提出来,括号里面就变成了(i+(i+1)+(i+2)+(i+3)+.....+右端点) 直接用等差数列来算就好
时间复杂度我不会算XD
Code
//Luogu P2261 [CQOI2007]余数求和
//Jul,7th
//取模运算推一推
#include<iostream>
#include<cstdio>
using namespace std;
int main(int argc, char **argv)
{
//freopen("sum.in","r",stdin);
//freopen("sum.out","w",stdout);
long long n,K;
scanf("%lld%lld",&n,&K); long long ans=n*K;
for(long long i=1;i<=n;i++)
{
long long temp=K/i;
long long l=i,r=n,mid,nxt=i;
while(l<=r)
{
mid=(l+r)/2;
if(K/mid==temp)
nxt=max(nxt,mid),l=mid+1;
else
r=mid-1;
}
ans-=(((i+nxt)*(nxt-i+1))/2)*temp;
i=nxt;
} printf("%lld",ans);
return 0;
}
正解(C++)
[Luogu P2261] [CQOI2007]余数求和 (取模计算)的更多相关文章
-
Luogu P2261 [CQOI2007]余数求和
最近中考放假几天都在怼一道BJOI2018的水题,但卡死在90pts跑不动啊! 然后今天发现终于过了然而Hack的数据全RE了然后就开始找新的题目来找回信心. 然后发现智能推荐里有这道题,然后想了1m ...
-
LUOGU P2261 [CQOI2007]余数求和(数论分块)
传送门 解题思路 数论分块,首先将 \(k\%a\) 变成 \(k-a*\left\lfloor\dfrac{k}{a}\right\rfloor\)形式,那么\(\sum\limits_{i=1}^ ...
-
洛谷——P2261 [CQOI2007]余数求和
P2261 [CQOI2007]余数求和 关键在于化简公式,题目所求$\sum_{i=1}^{n}k\mod i$ 简化式子,也就是$\sum_{i=1}^{n}(k-\frac{k}{i}\time ...
-
[Luogu 2261] CQOI2007 余数求和
[Luogu 2261] CQOI2007 余数求和 这一定是我迄今为止见过最短小精悍的省选题了,核心代码 \(4\) 行,总代码 \(12\) 行,堪比小凯的疑惑啊. 这题一看暴力很好打,然而 \( ...
-
洛谷 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]余数求和 二.分析 参考文章:click here 对于整除分块,最重要的是弄清楚怎样求的分得的每个块的范围. 假设$ n = 10 ,k = 5 $ $$ ...
-
[洛谷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]余数求和
我是题面 题意还是很清晰,很容易理解 1e9范围明显不能暴力,除非你能把常数优化到\(\frac1 {10}\),但我实在想象不到用了这么多取模怎么把常数优化下去 我们可以把\(k\%i\)变成\(k ...
随机推荐
-
Linux – Usermod命令参数解析和实例说明
usermod 命令修改系统帐户文件来反映通过命令行指定的变化 1. 首先看看usermod都是有哪些参数 [root@hxweb101 ~]$ usermod --help Usage: userm ...
-
rem是如何实现自适应布局的?
http://caibaojian.com/web-app-rem.html 使用rem 然后根据媒体查询实现自适应.跟使用JS来自适应适配也是同个道理,不过是js更精确一点.使用媒体查询: html ...
-
Visual Stuido 在文件中查找不显示结果
出现好几次了.解决方法如下: 注册表找到 HKEY_CLASSES_ROOT\Wow6432Node\CLSID\{73B7DC00-F498-4ABD-AB79-D07AFD52F395}\InPr ...
-
re模块使用
import re listall = "adkr20xcv3\actad4/" result = re.search('\w+',listall) print result.gr ...
-
HTML5 文件域+FileReader 分段读取文件并上传(七)-WebSocket
一.单文件上传实例 HTML: <div class="container"> <div class="panel panel-default" ...
-
JNI调用native方法出现 java.lang.UnsatisfiedLinkError: XXXclass.XXXmethod()异常的解决办法
昨天拿到JNI的Android工程Demo,然后把demo整合到开发的主线工程上,发现调用JNI方法一直抛同一个异常 java.lang.UnsatisfiedLinkError: XXXclass. ...
-
Spring execution表达式
execution(modifiers-pattern? ret-type-pattern declaring-type-pattern? name-pattern(param-pattern) th ...
-
GUI学习之五——QAbstractButton类学习笔记
今天总结一下AbstractButton类的学习笔记. 一.描述 AbstractButton是对各种按键的抽象类他的继承关系是这样的 首先,QAbstractButton继承了QWidget类的各种 ...
-
go标准库的学习-path/filepath
参考https://studygolang.com/pkgdoc 标准库path中有的该path/filepath库中都有,所以一般都使用path/filepath 导入方式: import &quo ...
-
Docker -d : Running modprobe bridge nf_nat failed with message: exit status 1
nf_nat 是做什么用的 - DockOne.iohttp://dockone.io/question/1384 docker-py的配置与使用 - openxxs - 博客园http://www. ...