Luogu

LOJ

分析

这个东西显然是有循环节的。

假设 $t_1$ 和 $t_2$ 两时刻 $x,y$ 相等，那么有
$$
\begin{cases}
t_1\equiv t_2\pmod{B}\\
t_1+\left\lfloor\frac{t_1}{B}\right\rfloor\equiv t_2+\left\lfloor\frac{t_2}{B}\right\rfloor\pmod{A}
\end{cases}
$$
令 $t_1<t_2$，则 $t_2=xB+t_1\;(x\in \mathbb{N}^*)$。

那么有
$$
\begin{aligned}
t_1+\left\lfloor\frac{t_1}{B}\right\rfloor&\equiv t_1+xB+\left\lfloor\frac{t_1+xB}{B}\right\rfloor\pmod{A}\\
t_1+\left\lfloor\frac{t_1}{B}\right\rfloor&\equiv t_1+xB+\left\lfloor\frac{t_1}{B}\right\rfloor+x\pmod{A}\\
xB+x&\equiv0\pmod{A}
\end{aligned}
$$
所以 $A|x(B+1)$，进一步得到
$$
\frac{A}{\gcd(A,B+1)}\Large\mid\normalsize x
$$
于是我们可以知道这个东西的最小循环节为
$$
\frac{AB}{\gcd(A,B+1)}
$$
那么如果输入的区间中有长度 $\geq$ 最小循环节长度的，直接输出最小循环节长度；否则问题变为区间覆盖，按左端点排序后扫一遍即可。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#define re register
#define int long long
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=2000000+10;

int n,A,B,L,cnt=0;
struct segment { int l,r; } s[N];
bool operator <(segment a,segment b) { return a.l<b.l; }

signed main() {
    n=read(),A=read(),B=read();
    L=A/__gcd(A,B+1)*B; if (L<0) L=2e18;
    for (re int i=1;i<=n;++i) {
        int l=read(),r=read();
        if (r-l+1>=L) { printf("%lld\n",L); return 0; }
        l%=L,r%=L;
        if (l<=r) s[++cnt]=(segment){l,r};
        else s[++cnt]=(segment){0,r},s[++cnt]=(segment){l,L-1};
    }
    sort(s+1,s+cnt+1); int mx=0,ans=0;
    for (re int i=1;i<=cnt;++i) {
        if (s[i].l>mx) ans+=s[i].l-mx;
        mx=max(mx,s[i].r+1);
    }
    if (mx<L) ans+=L-mx;
    printf("%lld\n",L-ans);
    return 0;
}