目录
显示
题目链接
https://www.luogu.com.cn/problem/P5444
题解
容易发现整个时间序列是有周期性的,我们设周期长度为 \(T\)。
接下来记 \(x=f(t)=(t+\left \lfloor\frac{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\frac{t}{B} \right \rfloor \equiv t+T+ \left \lfloor\frac{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)\) 区间上求若干条线段交大小的问题。
// 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; }