【洛谷5444】[APIO2019] 奇怪装置（数论）

点此看题面

• 给定(n)个值域区间和两个参数(A,B)。
• 从这些区间中任选一个数(x)，求能得到多少种不同的二元组(((x+lfloorfrac xB floor)\%A,x\%B))。
• (nle10^6,A,Ble10^{18})

从第二维入手

第一维(x+lfloorfrac xB floor)看上去非常恶心，而第二维(x\%B)就非常清新，因此容易想到从第二维入手。

从第二维入手，意味着按照模(B)的不同余数讨论。

相邻两个模(B)同余的数(x)相差(B)，则(x+lfloorfrac xB floor)必然相差(B+1)，因此实际上能发生变化的次数应该是(frac A{gcd(A,B+1)})。

结合上模(B)的余数共有(B)个，因此两个(x)对应的二元组相同当且仅当它们模(frac A{gcd(A,B+1)} imes B)同余。

令(P=min{frac A{gcd(A,B+1)} imes B,10^{18}+1})（若过大则存不下）。

如果存在一个区间满足(r-l+1ge P)，显然答案就是(P)了（然而一开始忘记判了依然过了！）。

否则，我们把所有区间左右端点向(P)取模，可能得到一个完整的区间或是一段后缀+一段前缀，后者可以视作两个完整的区间。

接下来就是要求所有区间的并集大小，直接按左端点排序维护出现过的最大右端点并统计答案即可。

代码：(O(nlogn))

#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 1000000
#define LL long long
using namespace std;
int n;LL A,B;I LL gcd(Con LL& x,Con LL& y) {return y?gcd(y,x%y):x;}
struct Q {LL l,r;I bool operator < (Con Q& o) Con {return l<o.l;}}q[2*N+5];
namespace FastIO
{
	#define FS 100000
	#define tc() (FA==FB&&(FB=(FA=FI)+fread(FI,1,FS,stdin),FA==FB)?EOF:*FA++)
	#define pc(c) (FC==FE&&(clear(),0),*FC++=c)
	int OT;char oc,FI[FS],FO[FS],OS[FS],*FA=FI,*FB=FI,*FC=FO,*FE=FO+FS;
	I void clear() {fwrite(FO,1,FC-FO,stdout),FC=FO;}
	Tp I void read(Ty& x) {x=0;W(!isdigit(oc=tc()));W(x=(x<<3)+(x<<1)+(oc&15),isdigit(oc=tc()));}
	Ts I void read(Ty& x,Ar&... y) {read(x),read(y...);}
	Tp I void writeln(Ty x) {W(OS[++OT]=x%10+48,x/=10);W(OT) pc(OS[OT--]);pc('
');}
}using namespace FastIO;
int main()
{
	RI i,t=0;read(n,A,B);LL l,r,P=min(1.0L*A/gcd(A,B+1)*B,1.0L+1e18);//求出P
	for(i=1;i<=n;++i) if(read(l,r),r-l+1>=P) return printf("%lld
",P),0;//如果区间长度大于等于P
	    else (l%=P)<=(r%=P)?q[++t]=(Q){l,r}:(q[++t]=(Q){l,P-1},q[++t]=(Q){0,r});//一个完整区间或一段后缀+一段前缀
	LL s=0,lst=-1;for(sort(q+1,q+t+1),i=1;i<=t;++i) s+=max(q[i].r-max(lst,q[i].l-1),0LL),lst=max(lst,q[i].r);//按左端点排序，求区间并集大小
	return printf("%lld
",s),0;
}