首页 > 其他分享 >数论分块

数论分块

时间:2023-05-18 22:12:03浏览次数:34  
标签:lfloor le frac 分块 数论 rfloor include Rightarrow

数论分块

数论分块就是一个小结论

对于一个常数n,和一个给定的数i(\(i <n\)),能使

\[\lfloor{\frac{n}{i}}\rfloor=\lfloor{\frac{n}{j}}\rfloor \]

的最大整数j(\(i\le j\le n\))为\(\lfloor{\frac{n}{\lfloor{\frac{n}{i}}\rfloor}}\rfloor{}\)

证明:设\(\lfloor{\frac{n}{i}}\rfloor=x\)

先需要证明\(\lfloor{\frac{n}{j}}\rfloor=x\)

一方面

\[jx=\lfloor{\frac{n}{x}}\rfloor x\le \frac{n}{x}\cdot x=n\\ \]

另一方面

\[\lfloor{\frac{n}{i}}\rfloor=x\Rightarrow \frac{n}{i}< x+1\Rightarrow\frac{n}{x+1} < i \le j\Rightarrow \frac{n}{j} < x+1 \]

因此

\[x\le \frac{n}{j} < x+1 \Rightarrow \lfloor{\frac{n}{j}}\rfloor=x \]

又因为

\[j=\lfloor{\frac{n}{x}}\rfloor{}>\frac{n}{x}-1 \Rightarrow (j+1)x>(\frac{n}{x}-1+1)x=n\Rightarrow \frac{n}{j+1} < x \]

因此,当\(j=\lfloor{\frac{n}{\lfloor{\frac{n}{i}}\rfloor}}\rfloor{}+1\)时不满足条件

所以我们得到了\(\lfloor{\frac{n}{i}}\rfloor\)所在块的右端点\(j=\lfloor{\frac{n}{\lfloor{\frac{n}{i}}\rfloor}}\rfloor{}\)

好了,我们已经知道了这个结论了,那我们如何使用呢?

数论分块可以计算一些关于\(\sum_{i=1}^nf(i)\lfloor{\frac{n}{i}}\rfloor\)的一些和式问题

我们只需要将数分成多个块,对于每个块,左端点为l,右端点为\(r=\lfloor{\frac{n}{\lfloor{\frac{n}{i}}\rfloor}}\rfloor{}\),这样可以减少时间复杂度。

例题

题意:

[CQOI2007]余数求和

题目描述

给出正整数 \(n\) 和 \(k\),请计算

\[G(n, k) = \sum_{i = 1}^n k \bmod i \]

思路:

我们可以将\(k \bmod i\)化简一下

\(k \bmod i=k-\lfloor{\frac{k}{i}}\rfloor\)

\[\sum_{i = 1}^n k \bmod i=\sum_{i = 1}^n(k-i\cdot\lfloor{\frac{k}{i}}\rfloor)=n*k-i\cdot\sum_{i = 1}^n\lfloor{\frac{k}{i}}\rfloor \]

代码

#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<cstring>
#include<queue>
#include<map>
#include<set>
using namespace std;
typedef long long ll;
int n,m;
ll read()
{
    ll x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
    while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
    return x*f;
}

int main()
{
    ll res;
    n = read();
    ll k = read();
    ll l = 1, r;
    res = n * k;
    while(l <= n)
    {
        if(l > k)
        {
            break; //i大于k时直接结束
        }
        else r = min(k / (k / l),(ll)n);//注意右端点不能超过n!
        res -= (r-l+1) * (k / l) *(l+r) / 2;
        l = r+1;//更新左端点
    }
    cout << res;
    return 0;
}

标签:lfloor,le,frac,分块,数论,rfloor,include,Rightarrow
From: https://www.cnblogs.com/Hunter19019/p/17413434.html

相关文章

  • 蒲公英(Loj 分块模板9)
    [Violet]蒲公英题目背景亲爱的哥哥:你在那个城市里面过得好吗?我在家里面最近很开心呢。昨天晚上奶奶给我讲了那个叫「绝望」的大坏蛋的故事的说!它把人们的房子和田地搞坏,还有好多小朋友也被它杀掉了。我觉得把那么可怕的怪物召唤出来的那个坏蛋也很坏呢。不过奶奶说他是很难受......
  • Loj分块模板1
    #include<iostream>#include<cstdio>#include<cmath>#include<cstring>#include<algorithm>usingnamespacestd;intn,m,len;intpos[5211314],add[5211314],num[5211314];inlinevoidAdd(intLiftPos,intRightPos,intval......
  • 初等数论——素数,逆元,EXGCD有关
    初等数论素数定义设整数\(p\ne0,\pm1\)。如果\(p\)除了平凡约数以外没有其他约数,那么称\(p\)为素数(不可约数)。若整数\(a\ne0,\pm1\)且\(a\)不是素数,则称\(a\)为合数。——————OIWiki素数的判定(素性测试)如何判断一个数\(x\)是不是质数?很显然我们可......
  • Codeforces 1423C - Dušan's Railway(树分块)
    首先\(k>3\)当\(k=3\)做,也就是说题目等价于找不超过\(10n\)条路径使得任意两点间的路径都可以表示为选定的这些路径中不相交的三者的并。先考虑链怎么做,关于这个\(3\),很自然的想法是取若干关键点,关键点之间两两连边,其余点再像相邻两关键点连边,因此考虑分块,每\(B\)个点设......
  • 数论小节
    @目录1.exgcd函数代码:使用格式:适用模式:1.求解方程2.欧拉函数函数代码:使用格式:适用模式:1.求解方程2.求解有限制的gcd3.(ex)BSGS函数代码:使用格式:适用范围:1.求解方程组4.整数分块代码:用法:5.莫比乌斯反演(思想)代码:用法:1.exgcd前提:gcd函数代码:longlonggcd(longlonga,longlong......
  • 230512 // 数论
    夺,夺少?哦,85pts,小让一手。A.征兵http://222.180.160.110:1024/contest/3574/problem/1GM说,怕久了不打最小生成树我们给忘了。笑话,就算退役十年我也不一定能忘了Kruskal,就算在役十年我也不一定能记住Prim。就一板板题,没什么好说的。#defineintlonglongnamespaceXSC......
  • 松下FP XH六轴标准程序,程序控制六个伺服,轴的点动控制,回零,相对定位,绝对定位,程序结构清
    松下FPXH六轴标准程序,程序控制六个伺服,轴的点动控制,回零,相对定位,绝对定位,程序结构清晰,分块编程通俗易懂,注释完整,程序是成熟的项目程序,多工位转盘循环控制,是转盘控制的经典作品ID:8119668632759622......
  • Codeforces 543E - Listening to Music(分块)
    根号log做法。能过CF的数据,但过不了校内模拟赛的数据/tuu考虑从\(f(i,x)\)到\(f(i+1,x)\)的变化在哪里:少了个\(a_i\)多了个\(a_{i+m}\),因此显然只有\(x\)在它俩中间才有\(f(i,x)\nef(i+1,x)\),即:\[f(i+1,x)-f(i,x)=\begin{cases}-1&(a_i<x\lea_{i+m})\\1&(a_{i+m......
  • 浅谈整除分块
    例题一\[\sum_{i=1}^n\lfloor\fracni\rfloor\\\]首先很容易想到直接求解,对于较大的数据,\(O(n)\)做法无法通过。注意到函数\(y=\lfloor\dfracnx\rfloor\)的图像如下:不难发现,随着\(x\)增大,\(y\)单调不增,这说明对于相同值的\(y\)总是分布在同一块区域。这启发我们根......
  • 一些数论知识
    欧拉函数定义$1-N$中与$N$互质的个数被称为欧拉函数,记为$φ(n)$。公式设$n={p_1}{c_1}*{p_2}\cdots^{c_m}$则$φ(n)=n\dfrac{p_1-1}{p_1}\dfrac{p_2-1}{p_2}\cdots\dfrac{p_m-1}{p_m}$性质$φ(1)=1$,因为$1$的质因数个数为$0$,所以原式$=1$$n$为质数,则$φ(n......