[APIO2019]奇怪装置。
题目
题解
先来证明一个引理。
(ac equiv bc(modp),(c,p)=d)则(a equiv b(mod frac{p}{d}))
(ecause ac ≡ bc(mod p))
( herefore p|ac-bc)
( herefore p|c(a-b))
(ecause (c,p)=d)
( herefore frac{p}{d}|frac{c}{d}(a-b))
(ecause c,p)已经除去了(gcd)，
( herefore (frac{p}{d},frac{c}{d})=1)
那么又(ecause)整除
( herefore frac{p}{d}|a-b)
即(a equiv b(mod frac{p}{d}))
正文开始。
我们想办法计算出(x=((t+lfloor frac{t}{B}
floor)modA))和(y=(t mod B))
当(t=k)时，假设(x=0,y=0)(当前是第一次循环，循环节就是(k))
把(t)换成(k)
则(x=((k+lfloor frac{k}{B}
floor)modA),y=(kmodB))
此时因为(y=0),所以(kmodB=0)，即(k|B)
那么(x)式子的下取整符号就可以去掉。
即
不难想出和(0 equiv frac{k(B+1)}{B}(modA))是等价的。
这时根据引理，把(frac{k}{B})当成引理中的(a)，把(B+1)当成引理中的(b)，把(A)当成引理中的(p)
得到
所以最小循环节(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
", 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
", ans);
return 0;
}