Studying Father's luogu blog

Focus on interest!

题解 P5444 【[APIO2019]奇怪装置】

容易发现整个时间序列是有周期性的,我们设周期长度为 $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)$ 区间上求若干条线段交大小的问题。

// 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;
}

2020-08-04 00:09:19 in 题解