题目
这种题目看上去就是有循环节的对吧。
在考场上，一个可行的方式是打表。
现在我们手推一下这个循环节。
记函数\(f(t)=(((t+\lfloor\frac tB\rfloor)\%A),(t\%B))\)，那么\(f(t_1)=f(t_2)\)的充要条件为：
\[
t_1+\lfloor\frac {t_1}B\rfloor\equiv t_2+\lfloor\frac {t_2}B\rfloor(mod\ A)
\]
\[
t_1\equiv t_2(mod\ B)
\]
看到第二个很熟悉的式子，我们不妨设\(t_2=t_1+xB(x>0)\)，代入第一个式子得到
\[
t_1+\lfloor\frac {t_1}B\rfloor\equiv t_1+xB+\lfloor\frac {t_1+xB}B\rfloor(mod\ A)
\]
后面那坨东西我们把它化简一下，拆开和左边的抵掉就变成了
\[
xB+x\equiv0(mod\ A)
\]
即
\[
A|x(B+1)
\]
把\(B+1\)移到左边去
\[
\frac{A(B+1)}{(A,B+1)}|x
\]
也就是说最小循环节为\(\frac{A(B+1)}{(A,B+1)}\)。
剩下的做一个简单的区间覆盖即可。
区间覆盖的话左端点升序排序，记录最大右端点即可。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
namespace IO
{
char ibuf[(1<<21)+1],*iS,*iT;
char Get(){return (iS==iT? (iT=(iS=ibuf)+fread(ibuf,1,(1<<21)+1,stdin),(iS==iT? EOF:*iS++)):*iS++);}
ll read(){ll x=0;int c=Get();while(!isdigit(c))c=Get();while(isdigit(c))x=x*10+c-48,c=Get();return x;}
}
using namespace IO;
const int N=1000007;
struct node{ll l,r;}a[N<<1];
int operator<(node a,node b){return a.l<b.l;}
ll max(ll a,ll b){return a>b? a:b;}
int main()
{
int n=read(),m=0,i;ll A=read(),B=read(),M=A/__gcd(A,B+1)*B,l,r,ans=0,mx=0;
for(i=1;i<=n;++i)
{
l=read(),r=read();
if(r-l+1>=M) return !printf("%lld",M);
l%=M,r%=M;
if(l>r) a[++m]=(node){0,r},a[++m]=(node){l,M-1}; else a[++m]=(node){l,r};
}
sort(a+1,a+m+1);
for(i=1;i<=m;++i)
{
if(a[i].l>mx) ans+=a[i].l-mx;
mx=max(mx,a[i].r+1);
}
if(mx<M) ans+=M-mx;
return !printf("%lld",M-ans);
}