自动搬运

查看原文

来自洛谷，原作者为

	Fading AFO

搬运于2025-08-24 22:10:49，当前版本为作者最后更新于2019-07-07 16:23:26，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

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

发现这个题目让我们求的点对$(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;
}