2020-2021:teams:legal_string:jxm2001:数论_1
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:jxm2001:数论_1 [2020/07/01 20:13] jxm2001 |
2020-2021:teams:legal_string:jxm2001:数论_1 [2020/07/27 22:56] (当前版本) jxm2001 ↷ 页面2020-2021:teams:legal_string:数论_1被移动至2020-2021:teams:legal_string:jxm2001:数论_1 |
||
|---|---|---|---|
| 行 1: | 行 1: | ||
| - | ====== 数论_1 ====== | + | ====== 数论 1 ====== |
| ===== 逆元递推 ===== | ===== 逆元递推 ===== | ||
| 行 17: | 行 17: | ||
| 两边同乘以 $r^{-1}$、$i^{-1}$，有 $i^{-1}\equiv -k\ast r^{-1}\pmod p$。 | 两边同乘以 $r^{-1}$、$i^{-1}$，有 $i^{-1}\equiv -k\ast r^{-1}\pmod p$。 | ||
| - | 即 $i^{-1}\equiv -\lfloor \frac pi\rfloor\ast (p\pmod i)^{-1}\pmod p$ | + | 即 $i^{-1}\equiv -\lfloor \frac pi\rfloor\ast (p\ \text{mod}\ i)^{-1}\pmod p$ |
| ==== 算法模板 ==== | ==== 算法模板 ==== | ||
| 行 39: | 行 39: | ||
| ==== 算法简介 ==== | ==== 算法简介 ==== | ||
| - | 数论分块用于解决形如 $\sum_{i=1}^n \lfloor \frac ni\rfloor$ 的问题，时间复杂度 $O(\sqrt n)$。 | + | 数论分块用于解决形如 $\sum_{i=1}^n a_if(\lfloor \frac ni\rfloor)$ 的问题，通过预处理 $a_i$ 前缀和，可以把时间复杂度降到 $O(\sqrt n)$。 |
| ==== 算法思想 ==== | ==== 算法思想 ==== | ||
| 行 57: | 行 57: | ||
| 关于算法的时间复杂度分析，有时间复杂度等于 $\lfloor \frac ni\rfloor$ 的可能取值个数。 | 关于算法的时间复杂度分析，有时间复杂度等于 $\lfloor \frac ni\rfloor$ 的可能取值个数。 | ||
| - | 当 $\lfloor \frac ni\rfloor \lt \sqrt n$ 时，显然这样的取值不超过 $\sqrt n$ 个。 | + | 当 $\lfloor \frac ni\rfloor \le \sqrt n$ 时，显然这样的取值不超过 $\sqrt n$ 个。 |
| 当 $\lfloor \frac ni\rfloor \gt \sqrt n$ 时，有 $i \lt \sqrt n$，所以这样的取值也不超过 $\sqrt n$ 个。 | 当 $\lfloor \frac ni\rfloor \gt \sqrt n$ 时，有 $i \lt \sqrt n$，所以这样的取值也不超过 $\sqrt n$ 个。 | ||
| 行 63: | 行 63: | ||
| 综上所述，$\lfloor \frac ni\rfloor$ 的可能取值个数只有 $O(\sqrt n)$ 个，时间复杂度证毕。 | 综上所述，$\lfloor \frac ni\rfloor$ 的可能取值个数只有 $O(\sqrt n)$ 个，时间复杂度证毕。 | ||
| + | ==== 算法模板 ==== | ||
| + | [[https://www.luogu.com.cn/problem/P2261|洛谷p2261]] | ||
| + | === 题意 === | ||
| + | |||
| + | 给定 $n$ 和 $k$，请计算 $\sum_{i=1}^n k\ mod \ i$ | ||
| + | |||
| + | === 题解 === | ||
| + | |||
| + | \begin{equation}\sum_{i=1}^n k\ mod \ i=\sum_{i=1}^n k-i\ast\lfloor \frac ki\rfloor=n\ast k-\sum_{i=1}^n i\ast\lfloor \frac ki\rfloor\end{equation} | ||
| + | |||
| + | <hidden 查看代码> | ||
| + | <code cpp> | ||
| + | LL pre_s(int k){return 1LL*k*(k+1)/2;} | ||
| + | LL cal(int i,int n){ | ||
| + | LL ans=0; | ||
| + | int lef=1,rig=0; | ||
| + | while(lef<=i){ | ||
| + | rig=min(i,n/(n/lef)); | ||
| + | ans+=(pre_s(rig)-pre_s(lef-1))*(n/lef); | ||
| + | lef=rig+1; | ||
| + | } | ||
| + | return ans; | ||
| + | } | ||
| + | int main() | ||
| + | { | ||
| + | LL n=read_int(),k=read_int(); | ||
| + | enter(n*k-cal(min(n,k),k)); | ||
| + | return 0; | ||
| + | } | ||
| + | </code> | ||
| + | </hidden> | ||
| + | |||
| + | ==== 算法练习 ==== | ||
| + | |||
| + | [[https://www.luogu.com.cn/problem/P2260|洛谷p2260]] | ||
| + | |||
| + | === 题意 === | ||
| + | |||
| + | 求 \begin{equation}\sum_{i=1}^n\sum_{j=1}^m [i\ne j](n\ mod\ i)\ast (m\ mod\ j)\pmod {19940417}\end{equation} | ||
| + | |||
| + | === 题解 === | ||
| + | |||
| + | 不妨设 $n\le m$。 | ||
| + | |||
| + | \begin{equation}\sum_{i=1}^n\sum_{j=1}^m [i\ne j](n\ mod\ i)\ast (m\ mod\ j)=\sum_{i=1}^n (n\ mod\ i)\ast\sum_{j=1}^m (m\ mod\ j)-\sum_{i=1}^n (n\ mod\ i)\ast (m\ mod\ i)\end{equation} | ||
| + | |||
| + | 前面两项解法同模板题，主要关注最后一项。 | ||
| + | |||
| + | \begin{equation}\sum_{i=1}^n (n\ mod\ i)\ast (m\ mod\ i)=\sum_{i=1}^n n\ast m-n\ast i\ast \lfloor\frac mi\rfloor-m\ast i\ast \lfloor\frac ni\rfloor+i^2\ast\lfloor\frac ni\rfloor\ast\lfloor \frac mi\rfloor\end{equation} | ||
| + | |||
| + | 类似的，也可以用数论分块解决，注意这条式子的最后一项需要同时处理 $n$ 和 $m$ 的分块边界。 | ||
| + | |||
| + | <hidden 查看代码> | ||
| + | <code cpp> | ||
| + | const int mod=19940417; | ||
| + | LL inv6; | ||
| + | LL exgcd(LL a,LL b,LL &tx,LL &ty){ | ||
| + | if(b==0){ | ||
| + | tx=1,ty=0; | ||
| + | return a; | ||
| + | } | ||
| + | LL re=exgcd(b,a%b,ty,tx); | ||
| + | ty-=a/b*tx; | ||
| + | return re; | ||
| + | } | ||
| + | LL pre_s_1(int k){return 1LL*k*(k+1)/2%mod;} | ||
| + | LL s_1(int lef,int rig){return (pre_s_1(rig)-pre_s_1(lef-1))%mod;} | ||
| + | LL pre_s_2(int k){return 1LL*k*(k+1)%mod*(2*k+1)%mod*inv6%mod;} | ||
| + | LL s_2(int lef,int rig){return (pre_s_2(rig)-pre_s_2(lef-1))%mod;} | ||
| + | LL cal_1(int i,int n){ | ||
| + | LL ans=0; | ||
| + | int lef=1,rig=0; | ||
| + | while(lef<=i){ | ||
| + | rig=min(i,n/(n/lef)); | ||
| + | ans=(ans+s_1(lef,rig)*(n/lef)%mod)%mod; | ||
| + | lef=rig+1; | ||
| + | } | ||
| + | return ans; | ||
| + | } | ||
| + | LL cal_2(int i,int n,int m){ | ||
| + | LL ans=0; | ||
| + | int lef=1,rig=0; | ||
| + | while(lef<=i){ | ||
| + | rig=min(i,min(n/(n/lef),m/(m/lef))); | ||
| + | ans=(ans+s_2(lef,rig)*(n/lef)%mod*(m/lef)%mod)%mod; | ||
| + | lef=rig+1; | ||
| + | } | ||
| + | return ans; | ||
| + | } | ||
| + | int main() | ||
| + | { | ||
| + | LL n=read_int(),m=read_int(),ans,t; | ||
| + | if(n>m) | ||
| + | swap(n,m); | ||
| + | exgcd(6,mod,inv6,t); | ||
| + | inv6%=mod; | ||
| + | ans=(n*n-cal_1(n,n))%mod*((m*m-cal_1(m,m))%mod)%mod; | ||
| + | ans=(ans-n*n%mod*m%mod)%mod; | ||
| + | ans=(ans+n*cal_1(n,m)%mod)%mod; | ||
| + | ans=(ans+m*cal_1(n,n)%mod)%mod; | ||
| + | ans=(ans-cal_2(n,n,m))%mod; | ||
| + | ans=(ans+mod)%mod; | ||
| + | enter(ans); | ||
| + | return 0; | ||
| + | } | ||
| + | </code> | ||
| + | </hidden> | ||
2020-2021/teams/legal_string/jxm2001/数论_1.1593605588.txt.gz · 最后更改: 2020/07/01 20:13 由 jxm2001
