题解 P5444 【[APIO2019]奇怪装置】
StudyingFather
2020-08-04 00:09:19
容易发现整个时间序列是有周期性的，我们设周期长度为 $T$。
接下来记 $x=f(t)=(t+\left \lfloor\dfrac{t}{B} \right \rfloor) \bmod A$，$y=g(t)=t \bmod B$。
由周期性的性质可得，$f(t)=f(t+T)$，$g(t)=g(t+T)$。即，
$$
t+\left \lfloor\dfrac{t}{B} \right \rfloor \equiv t+T+ \left \lfloor\dfrac{t+T}{B} \right \rfloor \pmod A
$$
以及，
$$
t \equiv t+T \pmod B
$$
发现 $g(t)$ 的等式较为简单，我们先从它入手。容易得到 $T \equiv 0 \pmod B$。
因此我们令 $T=kB$。
回代到 $f(t)$ 的等式中，得到（中间推导过程略），
$$
(B+1)k \equiv 0 \pmod A
$$
进一步得到，
$$
k=\frac{A}{\gcd(A,B+1)}
$$
从而得出，
$$
T=\frac{AB}{\gcd(A,B+1)}
$$
这样我们就把问题转变为了一个在 $[0,T)$ 区间上求若干条线段交大小的问题。
```cpp
// Problem: P5444 [APIO2019]奇怪装置
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P5444
// Memory Limit: 500 MB
// Time Limit: 4000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<long long,long long> pll;
vector<pll> v;
long long gcd(long long x,long long y)
{
return y==0?x:gcd(y,x%y);
}
int main()
{
ios::sync_with_stdio(false);
long long n,a,b;
cin>>n>>a>>b;
long long T=a/gcd(a,b+1);
if((__int128)T*b>=1e18)
T=1e18;
else
T*=b;
for(int i=1;i<=n;i++)
{
long long l,r;
cin>>l>>r;
if(r-l+1>=T)
{
cout<<T<<endl;
return 0;
}
l%=T,r%=T;
if(l<=r)
v.emplace_back(l,r);
else
v.emplace_back(l,T-1),v.emplace_back(0,r);
}
sort(v.begin(),v.end());
long long l=v[0].first,r=v[0].second,ans=0;
for(auto p:v)
if(p.first<=r)
r=max(r,p.second);
else
{
ans+=r-l+1;
l=p.first,r=p.second;
}
ans+=r-l+1;
cout<<ans<<endl;
return 0;
}
```