数学专题B1—同余

用户头像 发布于 2025-09-05 126 次阅读 OI

数学专题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<bits/stdc++.h>
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<=x){
    	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;
    cout<<(g(R)-g(L-1)+mod)%mod;
  	return 0;
}

P2312 解方程

注意到 $a_i$ 十分巨大，
可以想到等式左边和哈希很相似（就差取模了），
所以我们可以快读，读入时取模。
然后直接暴力即可。
代码：

#include<bits/stdc++.h>
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;i<=n;i++) a[i]=read();
	p[0]=1;
	for(int x=1;x<=m;x++){
		int now=a[0];
		for(int i=1;i<=n;i++) p[i]=(p[i-1]*x)%mod,(now+=a[i]*p[i])%=mod;
		if(now%mod==0) ans[++idx]=x;
	}
	cout<<idx<<endl;
	for(int i=1;i<=idx;i++) cout<<ans[i]<<endl;
	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<bits/stdc++.h>
using namespace std;
#define int long long
int L,R;
int g(int x){
	int ans=0,l=1;
	while(l<=x){
    	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;
	cout<<g(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<bits/stdc++.h>
using namespace std;
#define int long long
int a,b,ans;
int g(int x,int t){
	if(x<=t-1) 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;i<=b;i++) ans+=(i%2?-1:1)*(g(b,i)-g(a-1,i));
	cout<<ans;
	return 0;
}