「APIO2019」奇怪装置

找到循环就很简单了

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

因此总的循环就是$B+1$对于$A$的循环乘上$B$

即$\frac{A} {gcd(A,B+1)}\cdot B$

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

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

以下是快排版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define mp make_pair
char IO;
ll rd(){
	ll s=0;
	while(!isdigit(IO=getchar()));
	do s=(s<<1)+(s<<3)+(IO^'0');
	while(isdigit(IO=getchar()));
	return s;
}
int n,c,i;
ll A,B,ans,r=-1,L,R;
pair <ll,ll> S[2000010];
int main(){
	for(n=rd(),A=rd(),B=rd(),A=min(1.0*B*(A/__gcd(A,B+1)),1e18),i=1;i<=n;++i) {
		L=rd(),R=rd();
		if(R-L+1>=A) return printf("%lld\n",A),0;
		L%=A,R%=A;
		L<=R?S[++c]=mp(L,R):(S[++c]=mp(L,A-1),S[++c]=mp(0,R));
	}
	for(sort(S+1,S+c+1),i=1;i<=c;++i) if(r<=S[i].second) ans+=S[i].second-max(r,S[i].first-1),r=S[i].second;
	printf("%lld\n",ans);
}