数学专题B1—同余 P3935 Calculating 设 g(x)=\sum^x_{i=1}f(i)， \therefore \sum^r_{i=l}f(i)=g(r)-g(l-1)， 对于 g(x)， 枚举每一个因数出现的次数，并按照次数分块， 所以可以得到以下代码： #include using namespace std; #define int long long const int mod=998244353; int L,R; int g(int x){ int ans=0,l=1; while(l>L>>R; cout `#include using namespace std; #define int long long const int mod=998244353; int L,R; int g(int x){ int ans=0,l=1; while(l int t=x/l,r=(t==0?x:min(x/t,x)); (ans+=(r-l+1)*t)%=mod; l=r+1; } return ans; } signed main(){ cin>>L>>R; coutg(R)-g(L-1)+mod)%mod; return 0; } ` P2312 解方程 注意到 a_i 十分巨大， 可以想到等式左边和哈希很相似（就差取模了）， 所以我们可以快读，读入时取模。 然后直接暴力即可。 代码： #include using namespace std; #define int long long const int mod=1e9+7,N=105,M=1e6+5; int n,m,idx; int a[N],p[N],ans[M]; int read(){ int k=0,f=1; char c=getchar(); while(c'9'){ if(c=='-') f=-1; c=getchar(); } while(c>='0'&&c>n>>m; for(int i=0;i `#include using namespace std; #define int long long const int mod=1e9+7,N=105,M=1e6+5; int n,m,idx; int a[N],p[N],ans[M]; int read(){ int k=0,f=1; char c=getchar(); while(c'0'||c>'9'){ if(c=='-') f=-1; c=getchar(); } while(c>='0'&&c'9') k=(k*10+c-'0')%mod,c=getchar(); return k*f; } signed main(){ cin>>n>>m; for(int i=0;ia[i]=read(); p[0]=1; for(int x=1;x int now=a[0]; for(int i=1;ip[i]=(p[i-1]*x)%mod,(now+=a[i]*p[i])%=mod; if(now%mod==0) ans[++idx]=x; } cout for(int i=1;ians[i] return 0; }` P2424 约数和 观察到 f(x)=\sigma(x)， 不妨设 g(x)=\sum^x_{i=1}\sigma(i)， 所以 f(X)+f(X+1)+......+f(Y)=g(Y)-g(X-1)。 对于 g(x)， 同样枚举因数同时按数量分块，统计答案即可。 代码： #include using namespace std; #define int long long int L,R; int g(int x){ int ans=0,l=1; while(l>L>>R; cout `#include using namespace std; #define int long long int L,R; int g(int x){ int ans=0,l=1; while(l int t=x/l,r=(t==0?x:min(x/t,x)); ans+=(l+r)*(r-l+1)/2*t; l=r+1; } return ans; } signed main(){ cin>>L>>R; coutg(R)-g(L-1); return 0; } ` P4863 JerryC Loves Driving \begin{align} &\sum^B_{i=A} \sum^i_{j=1} \lfloor\frac{i}{j}\rfloor ×(-1)^j \\ =&\sum^B_{j=1}(-1)^j·\sum^B_{i=A} \lfloor\frac{i}{j}\rfloor \\ =&\sum^B_{j=1}(-1)^j·(\sum^B_{i=1} \lfloor\frac{i}{j}\rfloor-\sum^{A-1}_{i=1} \lfloor\frac{i}{j}\rfloor) \end{align} 设 g(x,t)=\sum^x_{i=1} \lfloor\frac{i}{t}\rfloor， 那么可以发现一个规律： 数列的前 t-1 个数一定是0 数列的结尾数字是 (x-t+1)/t，数量为 (x-t+1)\mod t。 数列中间数字每个数都连续出现 t 次。 所以可以根据规律 O(1) 求得 g(x,t)。 最终复杂度为 O(B)，代码如下： #include using namespace std; #define int long long int a,b,ans; int g(int x,int t){ if(x>a>>b; for(int i=1;i `#include using namespace std; #define int long long int a,b,ans; int g(int x,int t){ if(x1) return 0; int ed=(x-t+1)/t; return ed*(ed+1)/2*t+(x-t+1)%t*(ed+1); } signed main(){ cin>>a>>b; for(int i=1;i2?-1:1)*(g(b,i)-g(a-1,i)); cout return 0; } `
数学专题B1—同余
笔记