数论分块与整除相

引理一

$$\forall a,b,c\in\mathbb{Z},\left\lfloor\frac{a}{bc}\right\rfloor=\left\lfloor\frac{\left\lfloor\frac{a}{b}\right\rfloor}{c}\right\rfloor$$

略证:

\begin{split} &\frac{a}{b}=\left\lfloor\frac{a}{b}\right\rfloor+r(0\leq r<1)\\ \Rightarrow &\left\lfloor\frac{a}{bc}\right\rfloor =\left\lfloor\frac{a}{b}\cdot\frac{1}{c}\right\rfloor =\left\lfloor \frac{1}{c}\left(\left\lfloor\frac{a}{b}\right\rfloor+r\right)\right\rfloor =\left\lfloor \frac{\left\lfloor\frac{a}{b}\right\rfloor}{c} +\frac{r}{c}\right\rfloor =\left\lfloor \frac{\left\lfloor\frac{a}{b}\right\rfloor}{c}\right\rfloor\\ &&\square \end{split}

引理二

$$\forall n \in N, \left|\left\{ \lfloor \frac{n}{d} \rfloor \mid d \in N \right\}\right| \leq \lfloor 2\sqrt{n} \rfloor$$

$|V|$表示集合$V$的元素个数

略证:

对于$d \leq \left \lfloor \sqrt{n} \right \rfloor$,$\left \lfloor \frac{n}{d} \right \rfloor$有$\left \lfloor \sqrt{n} \right \rfloor$种取值.

对于$d \geq \left \lfloor \sqrt{n} \right \rfloor$,有$\left \lfloor \frac{n}{d} \right \rfloor \leq \left \lfloor \sqrt{n} \right \rfloor$,也只有$\left \lfloor \sqrt{n} \right \rfloor$种取值.

数论分块

数论分块的过程大概如下:考虑含有$\left \lfloor \frac{n}{i} \right \rfloor$的求和式子($n$为常数)

对于任意一个$i$($i \leq n$),我们需要找到一个最大的$j$($i \leq j \leq n$),使得$\left \lfloor \frac{n}{i} \right \rfloor = \left \lfloor \frac{n}{i} \right \rfloor$.

那么$j = \left \lfloor \frac{n}{\left \lfloor \frac{n}{i} \right \rfloor} \right \rfloor$.

略证:

\begin{split} &\left\lfloor\frac{n}{i}\right\rfloor \leq \frac{n}{i}\\ \Rightarrow &\left\lfloor\frac{n}{ \left\lfloor\frac{n}{i}\right\rfloor }\right\rfloor \geq \left\lfloor\frac{n}{ \frac{n}{i} }\right\rfloor = \left\lfloor i \right\rfloor=i \\ \Rightarrow &i\leq \left\lfloor\frac{n}{ \left\lfloor\frac{n}{i}\right\rfloor }\right\rfloor\\ &&\square \end{split}

即$j = \left \lfloor \frac{n}{\left \lfloor \frac{n}{i} \right \rfloor} \right \rfloor$.

利用上述结论,我们每次以$[i,j]$为一块,分块求和即可

原文地址:https://www.cnblogs.com/lfri/p/11173941.html

时间: 07-11

数论分块与整除相的相关文章

[BZOJ4815][CQOI4815]小Q的表格 数论+分块

题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=4815 题目中所给条件中的(a,a+b)和(a,b)的关系很瞩目. 然后大家都知道(a,b)=(a,a-b)=(a,a+b),于是观察(猜)一下这个表格与gcd的关系. 可以发现每次修改(a,b)会影响到所有(i,j)=(a,b)的点,并且关系为f(i,j)=(i/a)*(j/b)*f(a,b). 所以只需要知道f(g,g)的值记为f(g),就能推出其他的值. 然后慢慢推推推大概可以推到这

BZOJ 4815: [Cqoi2017]小Q的表格

Description \(b×f(a,a+b)=(a+b)*f(a,b)\),支持修改 求\(\sum_{i=1}^k\sum_{j=1}^kf(i,j)\) \(m\leqslant 10^4,k\leqslant n\leqslant 4\times 10^6\) Solution 数论+分块 可以发现这是一个类似于更相减损的东西...就是修改一个位置,只会影响与他横纵坐标相同的位置...所以它其实是一个一维的东西...所以就是求\(\sum_{i=1}^k\sum_{j=1}^k\fra

bzoj3930 [CQOI2015]选数

Description 我们知道,从区间[L,H](L和H为整数)中选取N个整数,总共有(H-L+1)^N种方案.小z很好奇这样选出的数的最大公约数的规律,他决定对每种方案选出的N个整数都求一次最大公约数,以便进一步研究.然而他很快发现工作量太大了,于是向你寻求帮助.你的任务很简单,小z会告诉你一个整数K,你需要回答他最大公约数刚好为K的选取方案有多少个.由于方案数较大,你只需要输出其除以1000000007的余数即可. Input 输入一行,包含4个空格分开的正整数,依次为N,K,L和H. O

BZOJ 4816 数字表格

首先是惯例的吐槽.SDOI题目名称是一个循环,题目内容也是一个循环,基本上过几年就把之前的题目换成另一个名字出出来,喜大普奔亦可赛艇.学长说考SDOI可以考出联赛分数,%%%. 下面放解题报告.并不喜欢打莫比鸟斯的解题报告就是因为公式编辑太鬼. 不知道多少分算法:简单模拟不解释. 正解一眼是莫比鸟斯函数,话说上次考莫比鸟斯就是去年吧,好像题目名也叫数字表格,只不过多了一个前缀"Crash的". 慢慢推吧,这里公式编辑器好像坏了?雾,贼慢. 假设n<=m;(if(n>m)sw

最大公约数之和——极限版II

P1490 - [UVa11426 ]最大公约数之和--极限版II Description Input 输入包含至多100组数据.每组数据占一行,包含正整数N(2<=N<=1<N<4000000).输入以N=0结束. Output 对于每组数据,输出一行,即所对应的G值.答案保证在64位带符号整数范围内. Sample Input 10 100 200000 0 Sample Output 67 13015 143295493160 Hint 数据范围: 对于30%的数据,2<

bzoj2956 模积和

Description 求∑∑((n mod i)*(m mod j))其中1<=i<=n,1<=j<=m,i≠j. Input 第一行两个数n,m. Output 一个整数表示答案mod 19940417的值 Sample Input 3 4 Sample Output 1 样例说明答案为(3 mod 1)*(4 mod 2)+(3 mod 1) * (4 mod 3)+(3 mod 1) * (4 mod 4) + (3 mod 2) * (4 mod 1) + (3 mod

POJ题目分类推荐 (很好很有层次感)

著名题单,最初来源不详.直接来源:http://blog.csdn.net/a1dark/article/details/11714009 OJ上的一些水题(可用来练手和增加自信) (POJ 3299,POJ 2159,POJ 2739,POJ 1083,POJ 2262,POJ 1503,POJ 3006,POJ 2255,POJ 3094) 初期: 一.基本算法: 枚举. (POJ 1753,POJ 2965) 贪心(POJ 1328,POJ 2109,POJ 2586) 递归和分治法. 递

暑假NOIP期末考试【1】—— Phantom

Phantom ?题目名称: phantom ?时间限制:1 秒 ?空间限制:256 MiB 题目描述 在一个无限大的棋盘上,排列着 n * n 枚棋子,形成一个 n 行 n 列的方阵.棋子可以横向或者纵向移动,移动方式是越过一个相邻的棋子,落入同一方向上的下一个空闲的格子里,同时,移除被越过的棋子.现在,我们想知道,是否有可能通过若干次操作,使得棋盘上仅剩一枚棋子. 例如,当 n = 2 时,有如下操作方法: -. -. -. -. .OO. => -O => -O => -. .OO

bzoj4916 神犇和蒟蒻

Description 很久很久以前,有一只神犇叫yzy; 很久很久之后,有一只蒟蒻叫lty; Input 请你读入一个整数N;1<=N<=1E9,A.B模1E9+7; Output 请你输出一个整数A=\sum_{i=1}^N{\mu (i^2)}; 请你输出一个整数B=\sum_{i=1}^N{\varphi (i^2)}; Sample Input 1 Sample Output 1 1 正解:杜教筛. 第一问答案是$1$. 第二问,先给个结论:$\varphi (n^{2})=n\va

BZOJ 4804: 欧拉心算

Description 求\(\sum_{i=1}^n\sum_{i=1}^n\varphi(gcd(i,j)),T\leqslant 5\times 10^3,n\leqslant 10^7\) Solution 数论分块+莫比乌斯反演. 化式子 \(\sum_{i=1}^n\sum_{i=1}^n\varphi(gcd(i,j))\)\(=\sum_d\varphi(d)\sum_{i=1}^n\sum_{j=1}^n[(i,j)=d]\)\(=\sum_d\varphi(d)(\sum_{