[Luogu P2261] [CQOI2007]余数求和 (取模计算)

时间:2022-09-04 10:27:34

题面

传送门:https://www.luogu.org/problemnew/show/P2261
[Luogu P2261] [CQOI2007]余数求和 (取模计算)

[Luogu P2261] [CQOI2007]余数求和 (取模计算)


Solution

这题显然有一个O(n)的直接计算法,60分到手。

接下来我们就可以拿出草稿纸推一推式子了

首先,取模运算在这里很不和谐,我们得转换一下。

对于任意取模计算,我们都有:

[Luogu P2261] [CQOI2007]余数求和 (取模计算)

所以,我们可以做以下推算

[Luogu P2261] [CQOI2007]余数求和 (取模计算)

经过一些手算,我们发现k/i(向下取整)是由一段一段的区间组成的,如下图

[Luogu P2261] [CQOI2007]余数求和 (取模计算)

显然,每段区间的右端点可以通过二分的方法来找

对于每一段区间,我们可以把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]余数求和 (取模计算)的更多相关文章

  1. Luogu P2261 &lbrack;CQOI2007&rsqb;余数求和

    最近中考放假几天都在怼一道BJOI2018的水题,但卡死在90pts跑不动啊! 然后今天发现终于过了然而Hack的数据全RE了然后就开始找新的题目来找回信心. 然后发现智能推荐里有这道题,然后想了1m ...

  2. LUOGU P2261 &lbrack;CQOI2007&rsqb;余数求和&lpar;数论分块&rpar;

    传送门 解题思路 数论分块,首先将 \(k\%a\) 变成 \(k-a*\left\lfloor\dfrac{k}{a}\right\rfloor\)形式,那么\(\sum\limits_{i=1}^ ...

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

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

  4. &lbrack;Luogu 2261&rsqb; CQOI2007 余数求和

    [Luogu 2261] CQOI2007 余数求和 这一定是我迄今为止见过最短小精悍的省选题了,核心代码 \(4\) 行,总代码 \(12\) 行,堪比小凯的疑惑啊. 这题一看暴力很好打,然而 \( ...

  5. 洛谷 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)\ ...

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

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

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

    洛谷题目链接:[CQOI2007]余数求和 题目背景 数学题,无背景 题目描述 给出正整数n和k,计算G(n, k)=k mod 1 + k mod 2 + k mod 3 + - + k mod n ...

  8. 洛谷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 ...

  9. P2261 &lbrack;CQOI2007&rsqb;余数求和

    我是题面 题意还是很清晰,很容易理解 1e9范围明显不能暴力,除非你能把常数优化到\(\frac1 {10}\),但我实在想象不到用了这么多取模怎么把常数优化下去 我们可以把\(k\%i\)变成\(k ...

随机推荐

  1. Linux – Usermod命令参数解析和实例说明

    usermod 命令修改系统帐户文件来反映通过命令行指定的变化 1. 首先看看usermod都是有哪些参数 [root@hxweb101 ~]$ usermod --help Usage: userm ...

  2. rem是如何实现自适应布局的?

    http://caibaojian.com/web-app-rem.html 使用rem 然后根据媒体查询实现自适应.跟使用JS来自适应适配也是同个道理,不过是js更精确一点.使用媒体查询: html ...

  3. Visual Stuido 在文件中查找不显示结果

    出现好几次了.解决方法如下: 注册表找到 HKEY_CLASSES_ROOT\Wow6432Node\CLSID\{73B7DC00-F498-4ABD-AB79-D07AFD52F395}\InPr ...

  4. re模块使用

    import re listall = "adkr20xcv3\actad4/" result = re.search('\w+',listall) print result.gr ...

  5. HTML5 文件域&plus;FileReader 分段读取文件并上传&lpar;七&rpar;-WebSocket

    一.单文件上传实例 HTML: <div class="container"> <div class="panel panel-default&quot ...

  6. JNI调用native方法出现 java&period;lang&period;UnsatisfiedLinkError&colon; XXXclass&period;XXXmethod()异常的解决办法

    昨天拿到JNI的Android工程Demo,然后把demo整合到开发的主线工程上,发现调用JNI方法一直抛同一个异常 java.lang.UnsatisfiedLinkError: XXXclass. ...

  7. Spring execution表达式

    execution(modifiers-pattern? ret-type-pattern declaring-type-pattern? name-pattern(param-pattern) th ...

  8. GUI学习之五——QAbstractButton类学习笔记

    今天总结一下AbstractButton类的学习笔记. 一.描述 AbstractButton是对各种按键的抽象类他的继承关系是这样的 首先,QAbstractButton继承了QWidget类的各种 ...

  9. go标准库的学习-path&sol;filepath

    参考https://studygolang.com/pkgdoc 标准库path中有的该path/filepath库中都有,所以一般都使用path/filepath 导入方式: import &quo ...

  10. Docker -d &colon; Running modprobe bridge nf&lowbar;nat failed with message&colon; exit status 1

    nf_nat 是做什么用的 - DockOne.iohttp://dockone.io/question/1384 docker-py的配置与使用 - openxxs - 博客园http://www. ...