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

· · 题解

显然这一类问题都有循环节。

发现这个题目让我们求的点对(x,y)

\left\{\begin{aligned}x\equiv t+\lfloor\frac tB\rfloor \pmod {A} \\y \equiv t\pmod {B} \end{aligned} \right.

我们设t_1,t_2两个时间点，所得到的(x,y)完全一致，即

\left\{\begin{aligned}t_1+\lfloor\frac {t_1}B\rfloor \equiv t_2+\lfloor\frac {t_2}B\rfloor \pmod {A} \\t_1 \equiv t_2\pmod {B} \end{aligned} \right.

不妨设t_1<t_2,则t_2=t_1+xB(x \in N^*)

代入上式

t_1+\lfloor\frac {t_1}B\rfloor \equiv t_1+xB+\lfloor\frac {t_1+xB}B\rfloor \pmod {A} t_1+\lfloor\frac {t_1}B\rfloor \equiv t_1+xB+\lfloor x+\frac {t_1}B\rfloor \pmod {A}

根据高斯函数的性质，原式化为

\lfloor\frac {t_1}B\rfloor \equiv xB+x+\lfloor\frac {t_1}B\rfloor \pmod {A} \therefore xB+x \equiv 0 \pmod {A} A|x(B+1)

根据整除的性质，或者提取最大公约数，得

\frac {A}{\gcd(A,B+1)}|x

所以只要满足这个式子，就可以满足对于任意t,t+Bx与t等价。

而且这个式子是强的，即不存在不满足这个式子依旧可以满足条件的x。

所以我们得到了我们想要的循环节Bx。显然x取\frac {A}{\gcd(A,B+1)}最小且满足条件。

此时\frac {AB}{\gcd(A,B+1)}就是我们要的最小循环节。

设最小循环节为G。

然后我们开始对每一个给定的区间[l,r]进行分类讨论：

情况1:

如果r-l+1 \geq G，则最终答案一定是G，直接退出程序。

情况2:

设L=l \bmod G,R=r \bmod G

如果L\leq R，因为这个情况不属于情况1（已经特判掉了）

所以我们可以取到这R-L+1个点对。

发现这正好是一个数轴线段覆盖问题。如果我们给所有点对进行编号(0\sim (G-1),即t\in [0,G-1] 时得到的点对)，并把编号抽象到数轴上，那么我们对线段[L,R]进行覆盖，就表示可以取到这些点。

情况3:

如果L>R，我们进行[0,R],[L,G-1]的区间覆盖。

最后整个数轴被覆盖的长度就是答案了。

实现

关于线段覆盖，我写了3种算法。

算法1:

动态开点线段树。

亲测只有20分 (loj)，64000000\times 3个\texttt{long long}你家评测机开的下？

算法2:

区间覆盖...珂朵莉树...岂不美哉？

loj 上过了（跑了最后一页），但是 luogu 不开 O2 过不去...

算法3:

由于懒得写 set ，我想到了一种类似贪心的方法。

所有要覆盖的线段按照左端点从小到大排序，然后从左向右扫，找到每一个连通块。

如果当前可以扩展到的右端点比这个线段的左端点小，说明已经有一个连通块了！答案加上连通块的长度即可。

这比上面两个快多了。

看不懂的可以看代码，包看包懂（滑稽）

代码如下（算法3，有注释）：

#include<bits/stdc++.h>
#define int long long
#define ll long long
using namespace std;
#ifdef Fading
#define gc getchar
#endif
#ifndef Fading
inline char gc(){
    static char now[1<<16],*S,*T;
    if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;}
    return *S++;
}
#endif
inline ll read(){
    register ll x=0,f=1;char ch=gc();
    while (!isdigit(ch)){if(ch=='-') f=-1LL;ch=gc();}
    while (isdigit(ch)){x=(x<<3LL)+(x<<1LL)+ch-'0';ch=gc();}
    return (f==1LL)?x:-x;
}
struct node{
    int l,r;
}g[2000001];
int tot;
inline bool cmp(node a,node b){
    return a.l<b.l;
}
signed main(){
    int n=read(),A=read(),B=read();
    int G=A/__gcd(A,B+1)*B;
    while (n--){
        int l=read(),r=read();
        if (r-l+1>=G){
            printf("%lld\n",G);return 0;
        }else{
            l=l%G,r=r%G;
            if (l>r){
                g[++tot].l=0;g[tot].r=r;
                g[++tot].l=l;g[tot].r=G-1;
            }else{
                g[++tot].l=l;g[tot].r=r;
            }
        }
    }
    sort(g+1,g+1+tot,cmp);
    int ans=0,nowL=g[1].l,nowR=g[1].r;
    g[tot+1].l=G+1;//新加入一个哨兵线段，把最后一个连通块算入总答案。
    for (int i=2;i<=tot+1;i++){
        if (nowR<g[i].l){//前面的线段已经形成了连通块
            ans+=nowR-nowL+1;nowL=g[i].l,nowR=g[i].r;
        }else{
            nowR=max(g[i].r,nowR);//更新可以扩展到的右端点，把这个线段加入连通块。
        }
    }
    printf("%lld\n",ans);
    return 0;
}