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

空の軌跡 · 2019-09-23 20:53:02 · 题解

这题很明显我们要求循环节，那么我们开始证明：

证明：

设 当前时间为 t，那么：

设 a×B 为最小的循环节 ( a 为非负整数 ) , 那么：

对于 y ，可见 a 的取值没有约束:

对于 x:

提出 x = ((t + \lfloor \frac{t}{B} \rfloor) \% A)：

可见需要满足 a×(B+1) 是 A 的整数倍

所以为使得 a 最小非负整数,

约分 a=n× \frac {\frac{A}{gcd(A,B+1)}} {\frac{B+1}{gcd(A,B+1)}}

可见 n 最小为 \frac{B+1}{gcd(A,B+1)}

此时 a 最小，

则最小循环节为 a×B=\frac{A×B}{gcd(A,B+1)}

注 : 如果你的循环节 <0 说明爆了 long long，直接设为 1e18+10就行

处理范围:

我们现在有了循环节，那么我们就可以处理了，

设 循环节为 xhj，以下的自行理解，思想很简单

对于l÷xhj==r÷xhj，我们把它改为 L=l\%xhj,R=r\%xhj 这个区间

对于l÷xhj==r÷xhj-1, 我们把它分为

两个区间

对于 l÷xhj<r÷xhj-1，很明显跨了整个区间，直接输出 xhj 走人

接下来就是线段覆盖求并集问题了，我们直接以 l 为关键字从小到大 sort , 并保存最远的 r , 然后按照顺序记录到 ans 就可以

代码:

#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
struct zxc
{
    long long l,r;
}qaq[3000010];
long long gcd(long long a,long long b)
{
    if(b==0)return a;
    return gcd(b,a%b);
}
bool cmp(zxc a,zxc b)
{
    return a.l<b.l;
}
inline long long read()
{
    long long a=0;
    char c=getchar();
    while(c>'9'||c<'0')c=getchar();
    while(c<='9'&&c>='0')
    {
        a=a*10+c-'0';
        c=getchar();
    }
    return a;
}
int main()
{
    int n,cnt;long long a,b,xhj;
    n=read();a=read();b=read();
    xhj=a/gcd(a,b+1)*b;
    cnt=n;
    if(xhj<0)xhj=1e18+10;
    for(register int i=1;i<=n;++i)
    {
        qaq[i].l=read();qaq[i].r=read();
        long long A=qaq[i].l/xhj,B=qaq[i].r/xhj;
        if(A==B)
        {
            qaq[i].l%=xhj;
            qaq[i].r%=xhj;
        }
        if(A==B-1)
        {
            qaq[++cnt].l=0;
            qaq[cnt].r=qaq[i].r%xhj;
            qaq[i].l=qaq[i].l%xhj;
            qaq[i].r=xhj-1;
        }
        if(A<B-1)
        {
            cout<<xhj;
            return 0;
        }
    }
    sort(qaq+1,qaq+cnt+1,cmp);
    long long ans=qaq[1].r-qaq[1].l+1,now=qaq[1].r;
    for(register int i=2;i<=cnt;++i)
    {
        if(qaq[i].r<=now)continue;
        ans+=qaq[i].r-max(qaq[i].l-1,now);
        now=qaq[i].r;
    }
    cout<<ans;
}