[洛谷 5444,loj 3144][APIO2019]奇怪装置

题目链接

https://www.luogu.com.cn/problem/P5444

https://loj.ac/problem/3144

题解

容易发现整个时间序列是有周期性的，我们设周期长度为 \(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;
}