[APIO 2010] [LOJ 3144] 奇怪装置 (数学)

题面

略

分析

考虑t1,t2时刻坐标相同的条件

\[\begin{cases} t_1+\lfloor \frac{t_1}{B} \rfloor \equiv t_2+\lfloor \frac{t_2}{B} \rfloor (\mathrm{mod}\ A) \\ t_1 \equiv t_2 (\mathrm{mod}\ B)\\ \end{cases}
\]

由第二个式子，可以令$t_1=t_2+Bk(k \in N)$

代入式子1，$t_2+Bk+\lfloor \frac{t_2}{B}+k \rfloor \equiv t_2+\lfloor \frac{t_2}{B} \rfloor(\mathrm{mod} \ A)$

消元得$(B+1)k \equiv 0 (\mathrm{mod} \ A)$

因此$k|\frac{A}{gcd(A,B+1)}$,

代入上式，$t_1=t_2+B\frac{A}{gcd(A,B+1)}(k \in N)$

$t_1 \equiv t _2 \ (\mathrm{mod} \frac{AB}{gcd(A,B+1)})$

因此，可以把l,r取模$\frac{AB}{gcd(A,B+1)}$,然后问题就变成在$[0,\frac{AB}{gcd(A,B+1)}]$上有若干条线段，求线段的并

直接排序再$O(n)$扫一遍即可

注意$\frac{AB}{gcd(A,B+1)}$可能会超过long long范围，但注意到l,r都$\leq 2 \times 10^{18}$,如果$\frac{AB}{gcd(A,B+1)}$超过就强行设成$ 2 \times 10^{18}$

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define maxn 1000000

#define maxr 2e18

using namespace std;

typedef long long ll;

ll n,A,B;

inline ll gcd(ll a,ll b){

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

}

struct seg{

	ll l;

	ll r;

	seg(){

	}

	seg(ll _l,ll _r){

		l=_l;

		r=_r;

	}

	friend bool operator < (seg p,seg q){

		if(p.l==q.l) return p.r<q.r;

		else return p.l<q.l;

	}

}a[maxn+5],b[maxn*2+5];

int cnt=0;

int main(){

	scanf("%I64d %I64d %I64d",&n,&A,&B);

	for(int i=1;i<=n;i++){

		scanf("%I64d %I64d",&a[i].l,&a[i].r);

	}

	ll C=A/gcd(A,B+1);

	if(maxr/B<=C) C=maxr; //B*C<=2e18

	else C=C*B;

	for(int i=1;i<=n;i++){

		if(a[i].r-a[i].l>=C){

			printf("%I64d\n",C);

			return 0;

		}

		if(a[i].l%C<=a[i].r%C){

			b[++cnt]=seg(a[i].l%C,a[i].r%C);

		}else{

			b[++cnt]=seg(0,a[i].r%C);

			b[++cnt]=seg(a[i].l%C,C-1);

		}

	}

	sort(b+1,b+1+cnt);

//	cnt=unique(b+1,b+1+cnt)-b-1;

	ll l=b[1].l,r=b[1].r;

	ll ans=0;

	for(int i=2;i<=cnt;i++){

		if(b[i].l>r+1){

			ans+=(r-l+1);

			l=b[i].l;

			r=b[i].r;

		}else if(b[i].r>r){

			r=b[i].r;

		}

	}

	ans+=r-l+1;

	printf("%I64d\n",ans);

}

巴特西

[APIO 2010] [LOJ 3144] 奇怪装置 (数学)

[APIO 2010] [LOJ 3144] 奇怪装置 (数学)

题面

分析

代码

最新文章

热门文章