整除分块（数论分块）

绝地灬酷狼 2021-11-01 03:40 530阅读 0赞

转载自此博客

整除分块：

给定n，求（Σd=1n ⌊n /d⌋）%998244353，n<=1e14

直接枚举会爆

考虑优化：

我们发现，⌊n/d⌋是有可能等于⌊n/(d+1)**⌋的**

那我们为什么要重复算呢？ 直接加就好了！！

那也就是说，对于一个i，我们要找到一个j，使得⌊n/i⌋=⌊n/(i+1)⌋=⌊n/(i+2)⌋=……=⌊n/j⌋!=n/(j+1)

那么，我们得出 j=⌊n/(⌊n/i⌋)⌋

于是就可以优化了，复杂度是O（sqrt（n））

代码实现：

  1. for(int i=1,j;i<=n;i=j+1)
  2. {
  3.     j=n/(n/i);
  4.     ans+=(j-i+1)*(n/i);
  5. }

是不是贼简单~~

转载于:https://www.cnblogs.com/mowanying/p/11276425.html

发表评论

表情：
评论列表 （有 0 条评论，530人围观）

还没有评论，来说两句吧...

相关阅读

    相关 分块算法

    1. 简介 存储系统的重复数据删除过程一般是这样的：首先将数据文件分割成一组数据块，为每个数据块计算指纹，然后以指纹为关键字进行Hash查找，匹配则表示该数据块为重复数据块，

    以你之姓@以你之姓@/ 0 赞/ 146 阅读

    相关 分块查找

    分块查找 算法思想 算法流程 分块查找又称索引顺序查找，它是顺序查找的一种改进方法。 时间复杂度：O(log(m)+n/m) 算法思想

    深碍√TFBOYSˉ_深碍√TFBOYSˉ_/ 0 赞/ 131 阅读

    相关 分块查找

    一 概述 分块查找又称作索引顺序查找，它吸取了顺序查找和折半查找各自的有点，既有动态结构，又适于快速查找。 二 分块查找的基本思想 将查找表分为若干子块，块内的元

    绝地灬酷狼绝地灬酷狼/ 0 赞/ 363 阅读

    相关 分块

    　　晚上脑子涨涨的，就总结一下最近写的分块入门9题吧。以下全是个人浅薄理解。 　　分块，一般就是把一组数据分成sqrt(n)块，然后根据题目要求，对其进行维护。基本要写的就是

    淩亂°似流年淩亂°似流年/ 0 赞/ 437 阅读