奇怪装置

找到循环就很简单了。

很显然 \(y\) 是每 \(B\) 次一循环的，对于每个相邻的 \(y\) 循环 \(x\) 的值均相差 \(B+1(\bmod A)\)。

因此总的循环就是 \(B+1\) 对于 \(A\) 的循环乘上 \(B\)。

即 \(\frac{A}{\gcd(A,B+1)} \times B\)。

知道循环节之后，把查询分成 \(O(n)\) 个区间，排序之后直接解决即可。

如果使用基数排序即可做到 \(O(n)\)。

以下是快排版本:

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e6+100;
int n,A,B,cnt,res;
int r=-1,L,R;
pair<int,int> s[N];
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n>>A>>B;
	A=min(1.0*B*(A/__gcd(A,B+1)),1e18);
	for(int i=1;i<=n;++i) {
		cin>>L>>R;
		if(R-L+1>=A){
			cout<<A;
			return 0;
		}
		L%=A;R%=A;
		if(L<=R) s[++cnt]=make_pair(L,R);
		else{
			s[++cnt]=make_pair(L,A-1);
			s[++cnt]=make_pair(0,R);
		}
	}
	sort(s+1,s+cnt+1);
	for(int i=1;i<=cnt;++i){
		if(r<=s[i].second){
			res+=s[i].second-max(r,s[i].first-1);
			r=s[i].second;
		}
	}
	cout<<res;
	return 0;
}