差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- technique:number_theory_sqrt_decomposition [2020/06/10 17:09]
admin fix sqrt
+++ technique:number_theory_sqrt_decomposition [2020/06/10 17:27] (当前版本)
admin fix link
@@ 行 29: / 行 29: @@
 </code>
-这是因为，C 语言的整数除法，恰好全部都是向下取整。（这里用中括号表示）
+这是因为，C 语言的整数除法，恰好全部都是向下取整。
 因此，关键就在于表达式 n/(n/l) 究竟是什么。即这个表达式：
-$$\lfloor\frac{n}{\lfloor\frac{n}{l}\rfloor}\rfloor$$
+$$\left\lfloor\frac{n}{\left\lfloor\frac{n}{l}\right\rfloor}\right\rfloor$$
 在“分块”计算的时候，**对于任意一个 d，我们需要找到一个最大的 r，使得 n/d=n/r。**目的是确定 d 落入了哪一块。
@@ 行 45: / 行 45: @@
 首先，n/(n/l) 不比给定的 l 小。这是显然的，把里面的取整符号放缩掉就行。
-$$\lfloor\frac{n}{\lfloor\frac{n}{l}\rfloor}\rfloor\geqslant\lfloor\frac{n}{\frac{n}{l}}\rfloor=l$$
+$$\left\lfloor\frac{n}{\left\lfloor\frac{n}{l}\right\rfloor}\right\rfloor\geqslant\left\lfloor\frac{n}{\frac{n}{l}}\right\rfloor=l$$
 然后，n/(n/l) 代入（迭代）原式，同理有：
-$$\lfloor\frac{n}{\lfloor\frac{n}{\lfloor\frac{n}{l}\rfloor}\rfloor}\rfloor\geqslant\lfloor\frac{n}{l}\rfloor$$
+$$\left\lfloor\frac{n}{\left\lfloor\frac{n}{\left\lfloor\frac{n}{l}\right\rfloor}\right\rfloor}\right\rfloor\geqslant\left\lfloor\frac{n}{l}\right\rfloor$$
 但是由于没取整前，图形是双曲线，n/x 这个函数是**单调不增**的。对于不同的 x 大小关系，代入函数后大小关系相反。这只能表明：
-$$\lfloor\frac{n}{\lfloor\frac{n}{\lfloor\frac{n}{l}\rfloor}\rfloor}\rfloor=\lfloor\frac{n}{l}\rfloor$$
+$$\left\lfloor\frac{n}{\left\lfloor\frac{n}{\left\lfloor\frac{n}{l}\right\rfloor}\right\rfloor}\right\rfloor=\left\lfloor\frac{n}{l}\right\rfloor$$
 这说明，l 和 n/(n/l) 一定位于同一块中。
@@ 行 59: / 行 59: @@
 怎么说明 n/(n/l) 是右端点？只要说明下一个邻居已经不落在区间里就行了。根据带余除法，有：
-$$\begin{aligned}n&=x\lfloor\frac{n}{x}\rfloor+r_1\\&=x\left(1+\lfloor\frac{n}{x}\rfloor\right)-(x-r_1)\\&=\left(1+\lfloor\frac{n}{x}\rfloor\right)\lfloor\frac{n}{1+\lfloor\frac{n}{x}\rfloor}\rfloor+r_2\end{aligned}$$
+$$\begin{aligned}n&=x\left\lfloor\frac{n}{x}\right\rfloor+r_1\\&=x\left(1+\left\lfloor\frac{n}{x}\right\rfloor\right)-(x-r_1)\\&=\left(1+\left\lfloor\frac{n}{x}\right\rfloor\right)\left\lfloor\frac{n}{1+\left\lfloor\frac{n}{x}\right\rfloor}\right\rfloor+r_2\end{aligned}$$
 其中，$r_2$ 非负，$x-r_1$ 是严格大于 0 的正整数。这样，我们就证明了：
-$$x\left(1+\lfloor\frac{n}{x}\rfloor\right)<\left(1+\lfloor\frac{n}{x}\rfloor\right)\lfloor\frac{n}{1+\lfloor\frac{n}{x}\rfloor}\rfloor$$
+$$x\left(1+\left\lfloor\frac{n}{x}\right\rfloor\right)<\left(1+\left\lfloor\frac{n}{x}\right\rfloor\right)\left\lfloor\frac{n}{1+\left\lfloor\frac{n}{x}\right\rfloor}\right\rfloor$$
 代入 x 为 n/l：
-$$\lfloor\frac{n}{l}\rfloor<\lfloor\frac{n}{1+\lfloor\frac{n}{\lfloor\frac{n}{l}\rfloor}\rfloor}\rfloor$$
+$$\left\lfloor\frac{n}{l}\right\rfloor<\left\lfloor\frac{n}{1+\left\lfloor\frac{n}{\left\lfloor\frac{n}{l}\right\rfloor}\right\rfloor}\right\rfloor$$
 n/l 严格比 n/(1+(n/(n/l))) 小，因此原命题也就证完了。
@@ 行 79: / 行 79: @@
 考虑表达式：n 和 n-1 除以 d 的商取整之差。
-$$\lfloor\frac{n}{d}\rfloor-\lfloor\frac{n-1}{d}\rfloor$$
+$$\left\lfloor\frac{n}{d}\right\rfloor-\left\lfloor\frac{n-1}{d}\right\rfloor$$
 根据带余除法的定义，有：
-$$n=d\lfloor\frac{n}{d}\rfloor+r_1$$
+$$n=d\left\lfloor\frac{n}{d}\right\rfloor+r_1$$
-$$n-1=d\lfloor\frac{n-1}{d}\rfloor+r_2$$
+$$n-1=d\left\lfloor\frac{n-1}{d}\right\rfloor+r_2$$
 $r_1$ 和 $r_2$ 是余数，都在 0 到 d-1 之间。因此这个表达式，仅当 d 整除 n 的时候相差 1，其他时候均为 0。
@@ 行 95: / 行 95: @@
 $$
-\sum_{i=1}^{n}(i,a)=\sum_{d|a}\lfloor\frac{n}{d}\rfloor\varphi(d)
+\sum_{i=1}^{n}(i,a)=\sum_{d|a}\left\lfloor\frac{n}{d}\right\rfloor\varphi(d)
 $$
 它的推论是：
-$$\sum_{i=l}^{r}(i,a)=\sum_{d|a}\left(\lfloor\frac{r}{d}\rfloor-\lfloor\frac{l-1}{d}\rfloor\right)\varphi(d)$$
+$$\sum_{i=l}^{r}(i,a)=\sum_{d|a}\left(\left\lfloor\frac{r}{d}\right\rfloor-\left\lfloor\frac{l-1}{d}\right\rfloor\right)\varphi(d)$$
 ====证明====
@@ 行 113: / 行 113: @@
 $$
-(n,a)=\sum_{d|a}\left(\lfloor\frac{n}{d}\rfloor-\lfloor\frac{n-1}{d}\rfloor\right)\varphi(d)
+(n,a)=\sum_{d|a}\left(\left\lfloor\frac{n}{d}\right\rfloor-\left\lfloor\frac{n-1}{d}\right\rfloor\right)\varphi(d)
 $$
@@ 行 124: / 行 124: @@
 $$
-\sum_{i=1}^n(\lfloor\sqrt[3]{i}\rfloor,i)\quad\mod 998244353\quad n\leq10^{21}
+\left[\sum_{i=1}^n(\left\lfloor\sqrt[3]{i}\right\rfloor,i)\right]\bmod{998244353}
 $$
+其中 $ n\leq10^{21}$。
 ==== 题解 ====
@@ 行 132: / 行 134: @@
 $$
-\sum^n_{i=1}(\lfloor\sqrt[3]{i}\rfloor,i)=\sum_{i=1}^{\lfloor\sqrt[3]{n}\rfloor-1}\sum_{j=i^3}^{(i+1)^3-1}(i,j)+\sum^n_{i=\lfloor\sqrt[3]{n}\rfloor^3}(\lfloor\sqrt[3]{n}\rfloor,i)
+\sum^n_{i=1}(\left\lfloor\sqrt[3]{i}\right\rfloor,i)=\sum_{i=1}^{\left\lfloor\sqrt[3]{n}\right\rfloor-1}\sum_{j=i^3}^{(i+1)^3-1}(i,j)+\sum^n_{i=\left\lfloor\sqrt[3]{n}\right\rfloor^3}(\left\lfloor\sqrt[3]{n}\right\rfloor,i)
 $$
@@ 行 138: / 行 140: @@
 $$
-\sum^n_{i=\lfloor\sqrt[3]{n}\rfloor^3}(\lfloor\sqrt[3]{n}\rfloor,i)=\sum_{d|\lfloor\sqrt[3]{n}\rfloor}\left(\lfloor\frac{n}{d}\rfloor-\lfloor\frac{\lfloor\sqrt[3]{n}\rfloor^3-1}{d}\rfloor\right)\varphi(d)
+\sum^n_{i=\left\lfloor\sqrt[3]{n}\right\rfloor^3}(\left\lfloor\sqrt[3]{n}\right\rfloor,i)=\sum_{d|\left\lfloor\sqrt[3]{n}\right\rfloor}\left(\left\lfloor\frac{n}{d}\right\rfloor-\left\lfloor\frac{\left\lfloor\sqrt[3]{n}\right\rfloor^3-1}{d}\right\rfloor\right)\varphi(d)
 $$
@@ 行 145: / 行 147: @@
 $$
 \begin{aligned}
-&\sum_{i=1}^{\lfloor\sqrt[3]{n}\rfloor-1}\sum_{j=i^3}^{(i+1)^3-1}(i,j)\\
+&\sum_{i=1}^{\left\lfloor\sqrt[3]{n}\right\rfloor-1}\sum_{j=i^3}^{(i+1)^3-1}(i,j)\\
-=&\sum_{i=1}^{\lfloor\sqrt[3]{n}\rfloor-1}\sum_{d|i}\left(\lfloor\frac{(i+1)^3-1}{d}\rfloor-\lfloor\frac{i^3-1}{d}\rfloor\right)\varphi(d)\\
+=&\sum_{i=1}^{\left\lfloor\sqrt[3]{n}\right\rfloor-1}\sum_{d|i}\left(\left\lfloor\frac{(i+1)^3-1}{d}\right\rfloor-\left\lfloor\frac{i^3-1}{d}\right\rfloor\right)\varphi(d)\\
-=&\sum_{d=1}^{\lfloor\sqrt[3]{n}\rfloor-1}\varphi(d)\sum_{x=1}^{\lfloor\frac{\lfloor\sqrt[3]{n}\rfloor-1}{d}\rfloor}\left(\lfloor\frac{(xd+1)^3-1}{d}\rfloor-\lfloor\frac{(xd)^3-1}{d}\rfloor\right)\\
+=&\sum_{d=1}^{\left\lfloor\sqrt[3]{n}\right\rfloor-1}\varphi(d)\sum_{x=1}^{\left\lfloor\frac{\left\lfloor\sqrt[3]{n}\right\rfloor-1}{d}\right\rfloor}\left(\left\lfloor\frac{(xd+1)^3-1}{d}\right\rfloor-\left\lfloor\frac{(xd)^3-1}{d}\right\rfloor\right)\\
-=&\sum_{d=1}^{\lfloor\sqrt[3]{n}\rfloor-1}\varphi(d)\sum_{x=1}^{\lfloor\frac{\lfloor\sqrt[3]{n}\rfloor-1}{d}\rfloor}\left(3dx^2+3x+1\right)
+=&\sum_{d=1}^{\left\lfloor\sqrt[3]{n}\right\rfloor-1}\varphi(d)\sum_{x=1}^{\left\lfloor\frac{\left\lfloor\sqrt[3]{n}\right\rfloor-1}{d}\right\rfloor}\left(3dx^2+3x+1\right)
 \end{aligned}
 $$
@@ 行 154: / 行 156: @@
 接下来就是平方和公式和等差数列求和，设仅与 d 相关的 y 为：
-$$y=\lfloor\frac{\lfloor\sqrt[3]{n}\rfloor-1}{d}\rfloor$$
+$$y=\left\lfloor\frac{\left\lfloor\sqrt[3]{n}\right\rfloor-1}{d}\right\rfloor$$
 得：
 $$
-\sum_{i=1}^{\lfloor\sqrt[3]{n}\rfloor-1}\sum_{j=i^3}^{(i+1)^3-1}(i,j)=\sum_{d=1}^{\lfloor\sqrt[3]{n}\rfloor-1}\varphi(d)d\frac{y(y+1)(2y+1)}{2}+\sum_{d=1}^{\lfloor\sqrt[3]{n}\rfloor-1}\varphi(d)(\frac{y(y+1)}{2}+y)
+\sum_{i=1}^{\left\lfloor\sqrt[3]{n}\right\rfloor-1}\sum_{j=i^3}^{(i+1)^3-1}(i,j)=\sum_{d=1}^{\left\lfloor\sqrt[3]{n}\right\rfloor-1}\varphi(d)d\frac{y(y+1)(2y+1)}{2}+\sum_{d=1}^{\left\lfloor\sqrt[3]{n}\right\rfloor-1}\varphi(d)(\frac{y(y+1)}{2}+y)
 $$
@@ 行 165: / 行 167: @@
 $$
-\sum^n_{i=1}(\lfloor\sqrt[3]{i}\rfloor,i)=\sum_{d=1}^{\lfloor\sqrt[3]{n}\rfloor-1}\varphi(d)d\frac{y(y+1)(2y+1)}{2}+\sum_{d=1}^{\lfloor\sqrt[3]{n}\rfloor-1}\varphi(d)(\frac{y(y+1)}{2}+y)+\sum_{d|\lfloor\sqrt[3]{n}\rfloor}\left(\lfloor\frac{n}{d}\rfloor-\lfloor\frac{\lfloor\sqrt[3]{n}\rfloor^3-1}{d}\rfloor\right)\varphi(d)
+\sum^n_{i=1}(\left\lfloor\sqrt[3]{i}\right\rfloor,i)=\sum_{d=1}^{\left\lfloor\sqrt[3]{n}\right\rfloor-1}\varphi(d)d\frac{y(y+1)(2y+1)}{2}+\sum_{d=1}^{\left\lfloor\sqrt[3]{n}\right\rfloor-1}\varphi(d)(\frac{y(y+1)}{2}+y)+\sum_{d|\left\lfloor\sqrt[3]{n}\right\rfloor}\left(\left\lfloor\frac{n}{d}\right\rfloor-\left\lfloor\frac{\left\lfloor\sqrt[3]{n}\right\rfloor^3-1}{d}\right\rfloor\right)\varphi(d)
 $$

CVBB ACM Team

用户工具

站点工具

差别

页面工具