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

· · 题解

先来证明一个引理。

ac \equiv bc(modp),(c,p)=d$则$a \equiv b(mod \frac{p}{d}) \because ac ≡ bc(mod p) \therefore p|ac-bc \therefore p|c(a-b) \because (c,p)=d \therefore \frac{p}{d}|\frac{c}{d}(a-b) $\therefore (\frac{p}{d},\frac{c}{d})=1

那么又\because整除

\therefore \frac{p}{d}|a-b

即a \equiv b(mod \frac{p}{d})
正文开始。
我们想办法计算出x=((t+\lfloor \frac{t}{B} \rfloor)modA)和y=(t mod B)
当t=k时，假设x=0,y=0(当前是第一次循环，循环节就是k)
把t换成k
则x=((k+\lfloor \frac{k}{B} \rfloor)modA),y=(kmodB)
此时因为y=0,所以kmodB=0，即k|B
那么x式子的下取整符号就可以去掉。
即

0=((k+\frac{k}{B})modA) 0=(\frac{k(B+1)}{B}modA)

不难想出和0 \equiv \frac{k(B+1)}{B}(modA)是等价的。
这时根据引理，把\frac{k}{B}当成引理中的a，把B+1当成引理中的b，把A当成引理中的p
得到

0 \equiv \frac{k}{B} (mod \frac{A}{gcd(A,B+1)}) 0 \equiv k (mod \frac{AB}{gcd(A,B+1)})

所以最小循环节k就是\frac{AB}{gcd(A,B+1)}。
做到这里恭喜你做完了这道题的一半。
我们考虑把这道题变成一道区间覆盖问题。
对区间[l,r]进行考虑
情况1：若r-l+1>=k
则说明此区间的长度已经大于了循环节，即循环节的每一个数都能取到，答案就是循环节，直接退出程序即可。
情况2：
将l和r都模k（下文的l和r都是模k之后的）
若l <= r
表示这段区间被完全包含在了循环节里面，即这条线段都可以取到。
我们在数轴上画一条l \sim r的线段。
情况三：
接着情况2，讨论l > r的情况
此时的情况是l到某一个点刚好结束了循环节，而这个点之后又重新开始了下一个循环，所以会出现l>r的情况。
我们在数轴上画2条线段。

[l,k - 1]$和$[0,r]

最后的答案就是数轴被覆盖的长度。
算这个东西就很简单了。
把所有线段按照左端点排序。
我们设nl,nr表示当前连通的线段的左端点和右端点。
之后枚举每1条线段。设当前枚举到的线段为L。 若L的左端点>nr则说明这条线段已经与当前连通的线段所断开了，我们将答案加上nr-nl+1，然后将nl和nr更新为这条线段的左端点和右端点即可。
否则说明这条线段也可以和当前已经连通的线段相连。
我们check \_ max一次nr和当前线段的右端点即可。（这部分配合着看我代码会更容易理解一些）

代码

#include <bits/stdc++.h>

const int maxn = 1e6 + 10;
typedef long long ll;

template<class t> inline void read(t& res) {
    res = 0;  char ch = getchar();  bool neg = 0;
    while (!isdigit(ch))
        neg |= ch == '-', ch = getchar();
    while (isdigit(ch))
        res = (res << 1) + (res << 3) + (ch & 15), ch = getchar();
    if (neg)
        res = -res;
}

ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }

ll n, m, i, j, k, A, B, sz, len, nl, nr;  
ll ans;   
struct line {
    ll l, r;     
    line() { l = r = 0; }
    line(ll _l, ll _r) { l = _l;  r = _r; }
    inline friend bool operator < (line a, line b) {
        return a.l < b.l;
    }
} l[maxn << 1];

int main() {
    read(n);  read(A);  read(B);
    len = A / gcd(A, B + 1) * B;  
    for (int i = 1; i <= n; i++) {
        ll le, ri;  read(le);  read(ri);
        if (ri - le + 1 >= len) { printf("%lld\n", len);  return 0; }
        le %= len;  
        ri %= len;
        if (le <= ri) 
            l[++sz] = line(le, ri);
        else
            l[++sz] = line(le, len - 1), 
            l[++sz] = line(0, ri);  
    }
    std::sort(l + 1, l + sz + 1);     
    l[++sz] = line(len + 1, 0);
    nl = l[1].l, nr = l[1].r;
    for (int i = 2; i <= sz; i++) {
        if (nr < l[i].l) {
            ans += nr - nl + 1;
            nl = l[i].l;
            nr = l[i].r;
        } else {
            nr = std::max(nr, l[i].r);
        }
    }
    printf("%lld\n", ans);
    return 0;   
}