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

· · 题解

我也是先膜拜一下参加APIO的大佬们orz，我因为NOIP太菜没能参加。。。

然后我无意间看到此题，神仙题！~

后来仔细推了推，发现不是很难。。过了一道APIO的题，毕竟机房大佬在考试当天就把这题切了，所以菜鸡在此写篇题解纪念一下。

这题上来就让人很懵，x和y毫无优美性质，数据也很不和谐：暴力只有15分。

对大佬来说这题一上来就找到正解切了，但本菜鸡不是一上来就推式子的人，所以我是把x和y都列出来了。。。

我们发现x这个数由两部分组成，我们将x分成2部分，x1 + x2.

x1 = t % A，x2 = ⌊t/B⌋ % A;

然后仔细把样例模拟一遍，比如A = 4，B = 5。

t  ： 0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 | 15

x1 ： 0  1  2  3  0  1  2  3  0  1  2  3  0  1  2  | 3
x2 ： 0  0  0  0  0 |1  1  1  1  1 |2  2  2  2  2  | 3
y  ： 0  1  2  3  4 |0  1  2  3  4 |0  1  2  3  4  | 0
x  :  0  1  2  3  0 |2  3  0  1  2 |0  1  2  3  0  | 2

接下来不难发现t%B和⌊t/B⌋的每一段长度都为B，我们用"|"将其隔开。

我们不难发现：x中的每一段，只要第一个数确定，后面的数都是顺着下来，也是确定的。所以对于一个t1与t2，其(x,y)相等，那么t1+1与t2+1的(x,y)也相等，比如上表中的0与10。

所以此题就是找一个循环节：最小的循环节使得两个数的（x，y）相等。

然后对于输入的每一段，mod B之后在循环节上找相应的位置，所有线段的交集的长度就是数对的个数。

循环节怎么找？ 这就很简单了：既然x与y都相等，那么首先y肯定得相等对吧，所以循环节长度是B的倍数。

x的增长规律很显然：每个数+1，过每一段再+1。

我们假设k段后出现相等的x，则

\begin{cases}t1+k+k*B=t2\\t1+k+k*B\equiv t1(mod\ A)\\(B+1)*k\equiv0(mod\ A)\end{cases}

求一个最小的k，他就是 gcd(B+1, A);\ \ 循环节长度就是B*k。

然后就好办了~，计算每一段询问在循环节上对应的位置，做一遍线段覆盖。按左端点排好序，更新最右端点的位置，我觉得肯定都会吧，具体在代码里。

此题还要注意一个细节：会不会爆long long？

肯定不会了~，t都没那么大怎么会爆？

但是你计算的循环节长度是A*B/gcd(B+1,A)的，是可以爆的，于是稍微处理一下，如果算出来的循环节长是负数，就把循环节改成无限大。

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#define QWQ cout<<"QwQ"<<endl;
#define ll long long 
#include<vector>
#include<queue>
#include<stack>
#include<map>
using namespace std;
const ll N=2001010;
const ll qwq=303030;
const ll inf=0x3f3f3f3f3f3f3f3f;
ll n,m;
ll H,R;
ll x,y;
ll A,B;
ll ans,cnt;
struct E{ ll l,r; } e[N];

inline ll read() {
    ll sum = 0; char c = getchar();
    while(c<'0' || c>'9') c = getchar();
    while(c>='0'&&c<='9') { sum = sum * 10 + c - '0'; c = getchar(); }
    return sum;
}

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

inline bool cmp(E aa,E bb) { return aa.l < bb.l; }

int main() {
    n = read(); A = read(); B = read();
    H = A / gcd(B+1,A) * B;
    if(H < 0) H = inf;            //爆long long
    for(int i=1;i<=n;i++) {
        x = read(); y = read();
        if(y-x+1>=H) { e[++cnt] = (E){0,H-1}; break; }                  //整个区间都能覆盖。
        x = x % H; y = y % H;
        if(y>=x) { e[++cnt] = (E){x,y}; }        //x，y在区间内。
        else {                //x，y在区间两遍。
            e[++cnt] = (E){0,y};
            e[++cnt] = (E){x,H-1};
        }
    }
    sort(e+1,e+cnt+1,cmp); R = e[1].r;
    for(int i=1;i<=cnt;i++) {
        ans += max((ll)0,e[i].l-R-1);
        R = max(R,e[i].r);
    }
    printf("%lld",H-(H-e[cnt].r)-e[1].l-ans+1);
    return 0;
}