technique:number_theory_sqrt_decomposition
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
technique:number_theory_sqrt_decomposition [2020/06/10 16:47] admin fix syntax |
technique:number_theory_sqrt_decomposition [2020/06/10 17:27] (当前版本) admin fix link |
||
|---|---|---|---|
| 行 29: | 行 29: | ||
| </code> | </code> | ||
| - | 这是因为，C 语言的整数除法，恰好全部都是向下取整。（这里用中括号表示） | + | 这是因为，C 语言的整数除法，恰好全部都是向下取整。 |
| 因此，关键就在于表达式 n/(n/l) 究竟是什么。即这个表达式： | 因此，关键就在于表达式 n/(n/l) 究竟是什么。即这个表达式： | ||
| - | $$\left[\frac{n}{\left[\frac{n}{l}\right]}\right]$$ | + | $$\left\lfloor\frac{n}{\left\lfloor\frac{n}{l}\right\rfloor}\right\rfloor$$ |
| 在“分块”计算的时候，**对于任意一个 d，我们需要找到一个最大的 r，使得 n/d=n/r。**目的是确定 d 落入了哪一块。 | 在“分块”计算的时候，**对于任意一个 d，我们需要找到一个最大的 r，使得 n/d=n/r。**目的是确定 d 落入了哪一块。 | ||
| 行 45: | 行 45: | ||
| 首先，n/(n/l) 不比给定的 l 小。这是显然的，把里面的取整符号放缩掉就行。 | 首先，n/(n/l) 不比给定的 l 小。这是显然的，把里面的取整符号放缩掉就行。 | ||
| - | $$\left[\frac{n}{\left[\frac{n}{l}\right]}\right]\geqslant\left[\frac{n}{\frac{n}{l}}\right]=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) 代入（迭代）原式，同理有： | 然后，n/(n/l) 代入（迭代）原式，同理有： | ||
| - | $$\left[\frac{n}{\left[\frac{n}{\left[\frac{n}{l}\right]}\right]}\right]\geqslant\left[\frac{n}{l}\right]$$ | + | $$\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 大小关系，代入函数后大小关系相反。这只能表明： | 但是由于没取整前，图形是双曲线，n/x 这个函数是**单调不增**的。对于不同的 x 大小关系，代入函数后大小关系相反。这只能表明： | ||
| - | $$\left[\frac{n}{\left[\frac{n}{\left[\frac{n}{l}\right]}\right]}\right]=\left[\frac{n}{l}\right]$$ | + | $$\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) 一定位于同一块中。 | 这说明，l 和 n/(n/l) 一定位于同一块中。 | ||
| 行 59: | 行 59: | ||
| 怎么说明 n/(n/l) 是右端点？只要说明下一个邻居已经不落在区间里就行了。根据带余除法，有： | 怎么说明 n/(n/l) 是右端点？只要说明下一个邻居已经不落在区间里就行了。根据带余除法，有： | ||
| - | $$\begin{aligned}n&=x\left[\frac{n}{x}\right]+r_1\\&=x\left(1+\left[\frac{n}{x}\right]\right)-(x-r_1)\\&=\left(1+\left[\frac{n}{x}\right]\right)\left[\frac{n}{1+\left[\frac{n}{x}\right]}\right]+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 的正整数。这样，我们就证明了： | 其中，$r_2$ 非负，$x-r_1$ 是严格大于 0 的正整数。这样，我们就证明了： | ||
| - | $$x\left(1+\left[\frac{n}{x}\right]\right)<\left(1+\left[\frac{n}{x}\right]\right)\left[\frac{n}{1+\left[\frac{n}{x}\right]}\right]$$ | + | $$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： | 代入 x 为 n/l： | ||
| - | $$\left[\frac{n}{l}\right]<\left[\frac{n}{1+\left[\frac{n}{\left[\frac{n}{l}\right]}\right]}\right]$$ | + | $$\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))) 小，因此原命题也就证完了。 | n/l 严格比 n/(1+(n/(n/l))) 小，因此原命题也就证完了。 | ||
| 行 79: | 行 79: | ||
| 考虑表达式：n 和 n-1 除以 d 的商取整之差。 | 考虑表达式：n 和 n-1 除以 d 的商取整之差。 | ||
| - | $$\left[\frac{n}{d}\right]-\left[\frac{n-1}{d}\right]$$ | + | $$\left\lfloor\frac{n}{d}\right\rfloor-\left\lfloor\frac{n-1}{d}\right\rfloor$$ |
| 根据带余除法的定义，有： | 根据带余除法的定义，有： | ||
| - | $$n=d\left[\frac{n}{d}\right]+r_1$$ | + | $$n=d\left\lfloor\frac{n}{d}\right\rfloor+r_1$$ |
| - | $$n-1=d\left[\frac{n-1}{d}\right]+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。 | $r_1$ 和 $r_2$ 是余数，都在 0 到 d-1 之间。因此这个表达式，仅当 d 整除 n 的时候相差 1，其他时候均为 0。 | ||
| 行 95: | 行 95: | ||
| $$ | $$ | ||
| - | \sum_{i=1}^{n}(i,a)=\sum_{d|a}\left[\frac{n}{d}\right]\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(\left[\frac{r}{d}\right]-\left[\frac{l-1}{d}\right]\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)$$ |
| ====证明==== | ====证明==== | ||
| 行 108: | 行 108: | ||
| $$ | $$ | ||
| (n,a)=\sum_{d|(a,n)}\varphi(d)=\sum_{d|a \&\& d|n}\varphi(d) | (n,a)=\sum_{d|(a,n)}\varphi(d)=\sum_{d|a \&\& d|n}\varphi(d) | ||
| - | $$ | + | $$ |
| 根据上面的讨论，有： | 根据上面的讨论，有： | ||
| $$ | $$ | ||
| - | (n,a)=\sum_{d|a}\left(\left[\frac{n}{d}\right]-\left[\frac{n-1}{d}\right]\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) |
| - | $$ | + | $$ |
| 利用数学归纳法对 n 归纳，或两边同时计算部分和，就证明了原命题。 | 利用数学归纳法对 n 归纳，或两边同时计算部分和，就证明了原命题。 | ||
| 行 124: | 行 124: | ||
| $$ | $$ | ||
| - | \sum_{i=1}^n(\left[^3\sqrt{i}\right],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}(\left[^3\sqrt{i}\right],i)=\sum_{i=1}^{\left[^3\sqrt{n}\right]-1}\sum_{j=i^3}^{(i+1)^3-1}(i,j)+\sum^n_{i=\left[^3\sqrt{n}\right]^3}(\left[^3\sqrt{n}\right],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) |
| - | $$ | + | $$ |
| - | 根据引理，对于原式右半部分的内容我们便可以通过数论分块在 $O(^6\sqrt{n})$ 的时间内解决。 | + | 根据引理，对于原式右半部分的内容我们便可以通过数论分块在 $O(\sqrt[6]{n})$ 的时间内解决。 |
| $$ | $$ | ||
| - | \sum^n_{i=\left[^3\sqrt{n}\right]^3}(\left[^3\sqrt{n}\right],i)=\sum_{d|\left[^3\sqrt{n}\right]}\left(\left[\frac{n}{d}\right]-\left[\frac{\left[^3\sqrt{n}\right]^3-1}{d}\right]\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} | \begin{aligned} | ||
| - | &\sum_{i=1}^{\left[^3\sqrt{n}\right]-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}^{\left[^3\sqrt{n}\right]-1}\sum_{d|i}\left(\left[\frac{(i+1)^3-1}{d}\right]-\left[\frac{i^3-1}{d}\right]\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}^{\left[^3\sqrt{n}\right]-1}\varphi(d)\sum_{x=1}^{\left[\frac{\left[^3\sqrt{n}\right]-1}{d}\right]}\left(\left[\frac{(xd+1)^3-1}{d}\right]-\left[\frac{(xd)^3-1}{d}\right]\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}^{\left[^3\sqrt{n}\right]-1}\varphi(d)\sum_{x=1}^{\left[\frac{\left[^3\sqrt{n}\right]-1}{d}\right]}\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} | \end{aligned} | ||
| - | $$ | + | $$ |
| 接下来就是平方和公式和等差数列求和，设仅与 d 相关的 y 为： | 接下来就是平方和公式和等差数列求和，设仅与 d 相关的 y 为： | ||
| - | $$y=\left[\frac{\left[^3\sqrt{n}\right]-1}{d}\right]$$ | + | $$y=\left\lfloor\frac{\left\lfloor\sqrt[3]{n}\right\rfloor-1}{d}\right\rfloor$$ |
| - | 得： | + | 得： |
| $$ | $$ | ||
| - | \sum_{i=1}^{\left[^3\sqrt{n}\right]-1}\sum_{j=i^3}^{(i+1)^3-1}(i,j)=\sum_{d=1}^{\left[^3\sqrt{n}\right]-1}\varphi(d)d\frac{y(y+1)(2y+1)}{2}+\sum_{d=1}^{\left[^3\sqrt{n}\right]-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) |
| - | $$ | + | $$ |
| y 也是一个除以 d 后取整的形式，故依旧可以用数论分块维护。总和式为： | y 也是一个除以 d 后取整的形式，故依旧可以用数论分块维护。总和式为： | ||
| $$ | $$ | ||
| - | \sum^n_{i=1}(\left[^3\sqrt{i}\right],i)=\sum_{d=1}^{\left[^3\sqrt{n}\right]-1}\varphi(d)d\frac{y(y+1)(2y+1)}{2}+\sum_{d=1}^{\left[^3\sqrt{n}\right]-1}\varphi(d)(\frac{y(y+1)}{2}+y)+\sum_{d|\left[^3\sqrt{n}\right]}\left(\left[\frac{n}{d}\right]-\left[\frac{\left[^3\sqrt{n}\right]^3-1}{d}\right]\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) |
| - | $$ | + | $$ |
| - | 通过 $O(^3\sqrt{n})$ 预处理出 $\varphi(i)i$ 的前缀和与 $\varphi(i)$ 的前缀和，就可以在 $O(^{6}\sqrt{n})$ 的时间内处理每一组询问了。总时间复杂度 $O(^3\sqrt{n}+^{6}\sqrt{n}*T)$。 | + | 通过 $O(\sqrt[3]{n})$ 预处理出 $\varphi(i)i$ 的前缀和与 $\varphi(i)$ 的前缀和，就可以在 $O(^{6}\sqrt{n})$ 的时间内处理每一组询问了。总时间复杂度 $O(\sqrt[3]{n}+^{6}\sqrt{n}*T)$。 |
| - | 注意，读入要用%%__%%int128，但是在开数组的时候都要开 ''int''，否则会爆空间。 | + | 注意，读入要用 ''%%__%%int128''，但是在开数组的时候都要开 ''int''，否则会爆空间。 |
| ====代码==== | ====代码==== | ||
| 行 202: | 行 204: | ||
| bool vis[maxN+10]; | bool vis[maxN+10]; | ||
| - | void calc()//线性筛计算欧拉函数 | + | void calc()//线性筛计算欧拉函数 |
| { | { | ||
| phi[1]=1; | phi[1]=1; | ||
| 行 213: | 行 215: | ||
| prime[++len]=i; | prime[++len]=i; | ||
| phi[i]=i-1; | phi[i]=i-1; | ||
| - | } | + | } |
| int j; | int j; | ||
| for(j=1;j<=len&&i*prime[j]<=maxN;j++) | for(j=1;j<=len&&i*prime[j]<=maxN;j++) | ||
| 行 224: | 行 226: | ||
| } | } | ||
| phi[i*prime[j]]=phi[i]*(prime[j]-1); | phi[i*prime[j]]=phi[i]*(prime[j]-1); | ||
| - | } | + | } |
| - | } | + | } |
| - | for(i=1;i<=maxN;i++)//欧拉函数乘自变量，其实也是个积性函数 | + | for(i=1;i<=maxN;i++)//欧拉函数乘自变量，其实也是个积性函数 |
| { | { | ||
| phii[i]=((long long)i*(long long)phi[i])%MOD; | phii[i]=((long long)i*(long long)phi[i])%MOD; | ||
| } | } | ||
| - | for(i=1;i<=maxN;i++)//部分和 | + | for(i=1;i<=maxN;i++)//部分和 |
| - | { | + | { |
| pre[i]=((long long)pre[i-1]+(long long)phi[i])%MOD; | pre[i]=((long long)pre[i-1]+(long long)phi[i])%MOD; | ||
| phii[i]=((long long)phii[i-1]+(long long)phii[i])%MOD; | phii[i]=((long long)phii[i-1]+(long long)phii[i])%MOD; | ||
| - | } | + | } |
| } | } | ||
| - | __int128 sqrt3(__int128 N)//二分 | + | __int128 sqrt3(__int128 N)//二分 |
| { | { | ||
| __int128 l=0,r=1e9; | __int128 l=0,r=1e9; | ||
| 行 267: | 行 269: | ||
| int t=sqrt3N/d; | int t=sqrt3N/d; | ||
| ans=(ans+(n/t-((__int128)sqrt3N*(__int128)sqrt3N*(__int128)sqrt3N-1)/t)%MOD*phi[t])%MOD; | ans=(ans+(n/t-((__int128)sqrt3N*(__int128)sqrt3N*(__int128)sqrt3N-1)/t)%MOD*phi[t])%MOD; | ||
| - | } | + | } |
| } | } | ||
| } | } | ||
| 行 273: | 行 275: | ||
| { | { | ||
| int x=(sqrt3N-1)/l; | int x=(sqrt3N-1)/l; | ||
| - | r=min(sqrt3N-1,(sqrt3N-1)/((sqrt3N-1)/l));//分块操作 | + | r=min(sqrt3N-1,(sqrt3N-1)/((sqrt3N-1)/l));//分块操作 |
| long long tmp1=(phii[r]-phii[l-1]+MOD)%MOD,tmp2=(pre[r]-pre[l-1]+MOD)%MOD; | long long tmp1=(phii[r]-phii[l-1]+MOD)%MOD,tmp2=(pre[r]-pre[l-1]+MOD)%MOD; | ||
| ans=(ans+tmp1*(long long)inv2%MOD*x%MOD*(x+1)%MOD*(2*x+1))%MOD; | ans=(ans+tmp1*(long long)inv2%MOD*x%MOD*(x+1)%MOD*(2*x+1))%MOD; | ||
technique/number_theory_sqrt_decomposition.1591778847.txt.gz · 最后更改: 2020/06/10 16:47 由 admin
