数论知识点整理

贝祖定理

素数筛法

欧拉函数

数论分块

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e9;
struct node{
	int ls,rs,val;
}d[6000005];
int n,g,r,mod,l[200005],s[200005],t[200005];
int query(int &p,int l,int r,int s,int t){
	if(!p)return 1e15;
	if(s<=l&&r<=t)return d[p].val;
	int mid=l+r>>1;
	int minn=1e15;
	if(s<=mid)minn=min(minn,query(d[p].lson,l,mid,s,t));
	if(mid+1<=t)minn=min(minn,query(d[p].rson,mid+1,r,s,t));
	return minn;
}
signed main(){
	cin>>n>>g>>r;
	mod=g+r;
	for(int i=1;i<=n+1;i++){
		cin>>l[i];
		s[i]=s[i-1]+l[i];
	}
	for(int i=n;i>=1;i--){
		int p=1;
		int nxt=min(query(p,1,N,g-t,mod-t-1),query(p,1,N,g+mod-t,N));
		if(nxt==1e15)t[i]=s[n]-s[i];
		else t[i]=s[nxt]-s[i]+mod-(s[nxt]-s[i])%mod+t[nxt];
	}
}