【APIO2019】奇怪装置(模意义下循环节)

传送门


原来APIO也有签到题

题解:

首先分析性质,整除同余问题里面有计数那最重要的肯定就是循环节。

考虑一下什么时候 t1t_1t1​ 和 t2t_2t2​ 形成的数对相同。

{t1+t1Bt2+t2B(modA)t1t2(modB) \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. ⎩⎨⎧​t1​+⌊Bt1​​⌋t1​​≡≡​​t2​+⌊Bt2​​⌋t2​​(modA)(modB)​

t2=t1+Bxt_2=t_1+B\cdot xt2​=t1​+B⋅x,考虑第一个式子:

t1+t1Bt1+Bx+t1+BxB(modA)Ax(B+1) \begin{aligned} t_1+\lfloor\frac{t_1}{B}\rfloor&\equiv t_1+B\cdot x+\lfloor\frac{t_1+B\cdot x}{B}\rfloor&\pmod A\\ A&\mid x(B+1)\\ \end{aligned} t1​+⌊Bt1​​⌋A​≡t1​+B⋅x+⌊Bt1​+B⋅x​⌋∣x(B+1)​(modA)​

其实很容易发现了xxx的合法取值就是Agcd(A,B+1)x\dfrac{A}{\gcd(A,B+1)}|xgcd(A,B+1)A​∣x,并且容易循环节就是tt+Bxt\rightarrow t+B\cdot xt→t+B⋅x,则最小循环节长度就是ABgcd(A,B+1)\dfrac{AB}{\gcd(A,B+1)}gcd(A,B+1)AB​。

则中间的部分很容易转化成线段覆盖,直接按照左端点排个序然后覆盖就行了。

注意循环节长度可能炸long long ,直接和最大的右端点取一下min即可。


代码:

#include<bits/stdc++.h>
#define ll long long
#define re register
#define cs const

namespace IO{
	inline char gc(){
		static cs int Rlen=4e7+7;
		static char buf[Rlen],*p1,*p2;
		return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,Rlen,stdin),p1==p2)?EOF:*p1++;
	}
	
	template<typename T>
	inline T get(){
		char c;T num;
		while(!isdigit(c=gc()));num=c^48;
		while(isdigit(c=gc()))num=(num+(num<<2)<<1)+(c^48);
		return num;
	}
	inline int gi(){return get<int>();}
	inline ll gl(){return get<ll>();}
}
using namespace IO;

using std::cerr;
using std::cout;
using pii=std::pair<ll,ll>;
#define fi first
#define se second

int n;ll A,B,M;
std::vector<pii> vec;

signed main(){
#ifdef zxyoi
	freopen("machine.in","r",stdin);
#endif
	n=gi(),A=gl(),B=gl();
	M=std::min(1.*A/std::__gcd(A,B+1)*B,1e18+5);
	while(n--){
		ll l=gl(),r=gl();
		if(r-l+1>=M){
			cout<<M,exit(0);
		}if(r>=M)l%=M,r%=M;
		if(l<=r)vec.push_back(pii(l,r));
		else vec.push_back(pii(0,r)),vec.push_back(pii(l,M-1));
	}
	ll nl=0,nr=-1,ans=0;
	std::sort(vec.begin(),vec.end());
	for(auto &t:vec){
		if(t.fi<=nr)nr=std::max(nr,t.se);
		else ans+=nr-nl+1,nl=t.fi,nr=t.se;
	}ans+=nr-nl+1;cout<<ans;
	return 0;
}
上一篇:P5445-[APIO2019]路灯【set,树状数组套线段树】


下一篇:【文文殿下】APIO2019游记