2020-2021:teams:legal_string:jxm2001:数论_1
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:jxm2001:数论_1 [2020/07/02 21:12] 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 |
||
|---|---|---|---|
| 行 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)$。 |
| ==== 算法思想 ==== | ==== 算法思想 ==== | ||
| 行 77: | 行 77: | ||
| <hidden 查看代码> | <hidden 查看代码> | ||
| <code cpp> | <code cpp> | ||
| - | #include <cstdio> | ||
| - | #include <iostream> | ||
| - | #include <vector> | ||
| - | #include <algorithm> | ||
| - | #include <cstring> | ||
| - | #include <cctype> | ||
| - | #include <queue> | ||
| - | #include <cmath> | ||
| - | #define _for(i,a,b) for(int i=(a);i<(b);++i) | ||
| - | #define _rep(i,a,b) for(int i=(a);i<=(b);++i) | ||
| - | #define mem(a,b) memset((a),(b),sizeof(a)) | ||
| - | using namespace std; | ||
| - | typedef long long LL; | ||
| - | inline int read_int(){ | ||
| - | int t=0;bool sign=false;char c=getchar(); | ||
| - | while(!isdigit(c)){sign|=c=='-';c=getchar();} | ||
| - | while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();} | ||
| - | return sign?-t:t; | ||
| - | } | ||
| - | inline LL read_LL(){ | ||
| - | LL t=0;bool sign=false;char c=getchar(); | ||
| - | while(!isdigit(c)){sign|=c=='-';c=getchar();} | ||
| - | while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();} | ||
| - | return sign?-t:t; | ||
| - | } | ||
| - | inline void write(LL x){ | ||
| - | register char c[21],len=0; | ||
| - | if(!x)return putchar('0'),void(); | ||
| - | if(x<0)x=-x,putchar('-'); | ||
| - | while(x)c[++len]=x%10,x/=10; | ||
| - | while(len)putchar(c[len--]+48); | ||
| - | } | ||
| - | inline void space(LL x){write(x),putchar(' ');} | ||
| - | inline void enter(LL x){write(x),putchar('\n');} | ||
| LL pre_s(int k){return 1LL*k*(k+1)/2;} | LL pre_s(int k){return 1LL*k*(k+1)/2;} | ||
| - | LL cal(int n,int k){ | + | LL cal(int i,int n){ |
| LL ans=0; | LL ans=0; | ||
| int lef=1,rig=0; | int lef=1,rig=0; | ||
| - | while(lef<=n){ | + | while(lef<=i){ |
| - | rig=min(n,k/(k/lef)); | + | rig=min(i,n/(n/lef)); |
| - | ans+=(pre_s(rig)-pre_s(lef-1))*(k/lef); | + | ans+=(pre_s(rig)-pre_s(lef-1))*(n/lef); |
| lef=rig+1; | lef=rig+1; | ||
| } | } | ||
| 行 153: | 行 119: | ||
| <hidden 查看代码> | <hidden 查看代码> | ||
| <code cpp> | <code cpp> | ||
| - | #include <cstdio> | ||
| - | #include <iostream> | ||
| - | #include <vector> | ||
| - | #include <algorithm> | ||
| - | #include <cstring> | ||
| - | #include <cctype> | ||
| - | #include <queue> | ||
| - | #include <cmath> | ||
| - | #define _for(i,a,b) for(int i=(a);i<(b);++i) | ||
| - | #define _rep(i,a,b) for(int i=(a);i<=(b);++i) | ||
| - | #define mem(a,b) memset((a),(b),sizeof(a)) | ||
| - | using namespace std; | ||
| - | typedef long long LL; | ||
| - | inline int read_int(){ | ||
| - | int t=0;bool sign=false;char c=getchar(); | ||
| - | while(!isdigit(c)){sign|=c=='-';c=getchar();} | ||
| - | while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();} | ||
| - | return sign?-t:t; | ||
| - | } | ||
| - | inline LL read_LL(){ | ||
| - | LL t=0;bool sign=false;char c=getchar(); | ||
| - | while(!isdigit(c)){sign|=c=='-';c=getchar();} | ||
| - | while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();} | ||
| - | return sign?-t:t; | ||
| - | } | ||
| - | inline void write(LL x){ | ||
| - | register char c[21],len=0; | ||
| - | if(!x)return putchar('0'),void(); | ||
| - | if(x<0)x=-x,putchar('-'); | ||
| - | while(x)c[++len]=x%10,x/=10; | ||
| - | while(len)putchar(c[len--]+48); | ||
| - | } | ||
| - | inline void space(LL x){write(x),putchar(' ');} | ||
| - | inline void enter(LL x){write(x),putchar('\n');} | ||
| const int mod=19940417; | const int mod=19940417; | ||
| LL inv6; | LL inv6; | ||
2020-2021/teams/legal_string/jxm2001/数论_1.1593695577.txt.gz · 最后更改: 2020/07/02 21:12 由 jxm2001
