数学专题B1—同余

P3935 Calculating

设 $g\left(x\right)=\sum _{i=1}^{x}f\left(i\right)$， $\mathrm{\therefore }\sum _{i=l}^{r}f\left(i\right)=g\left(r\right)-g(l-1)$， 对于 $g\left(x\right)$， 枚举每一个因数出现的次数，并按照次数分块， 所以可以得到以下代码：

#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\left(x\right)=\sigma \left(x\right)$， 不妨设 $g\left(x\right)=\sum _{i=1}^x\sigma \left(i\right)$， 所以 $f\left(X\right)+f(X+1)+......+f\left(Y\right)=g\left(Y\right)-g(X-1)$。 对于 $g\left(x\right)$， 同样枚举因数同时按数量分块，统计答案即可。 代码：

#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{array}{ll}& amp;\sum _{i=A}^B\sum _{j=1}^i\lfloor \frac{i}{j}\rfloor \mathrm{\times }(-1{)}^j\\ =& amp;\sum _{j=1}^B(-1{)}^j\mathrm{·}\sum _{i=A}^B\lfloor \frac{i}{j}\rfloor \\ =& amp;\sum _{j=1}^B(-1{)}^j\mathrm{·}(\sum _{i=1}^B\lfloor \frac{i}{j}\rfloor -\sum _{i=1}^{A-1}\lfloor \frac{i}{j}\rfloor )\end{array}$$ 设 $g(x,t)=\sum _{i=1}^x\lfloor \frac{i}{t}\rfloor$， 那么可以发现一个规律：

• 数列的前 $t-1$ 个数一定是0

• 数列的结尾数字是 $(x-t+1)/t$，数量为 $(x-t+1)\text{[PARSE ERROR: Undefined("Command("mod")")]}t$。

• 数列中间数字每个数都连续出现 $t$ 次。

所以可以根据规律 $O\left(1\right)$ 求得 $g(x,t)$。 最终复杂度为 $O\left(B\right)$，代码如下：

#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;
} `