Lucky Days

better look

给定 $l_a,r_a,t_a,l_b,r_b,t_b$,对于所有的非负整数 $k$,将区间 $[l_a+k{t}_a,r_a+k{t}_a]$ 打上标记 $1$,将区间 $[l_b+k{t}_b,r_b+k{t}_b]$ 打上标记 $2$.Find the longest continuous interval such that all positions in the interval are marked at the same time $1,2$ 标记.

样例一

0 2 5
1 3 5

2

样例二

0 1 3
2 3 6

1

思路

The question requires the length of the maximum coincidence between the two intervals.

First, let's think about the first point：To maximize the coincidence of the two intervals,The two intervals need to be as close as possible.The optimal case is two intervalsThe left endpoints are as equal as possible,This is the maximum degree of overlap.

即使 $la+x\ast ta=lb+y\ast tb$

Shift the equation to get $x\ast ta-y\ast tb=lb-la$ （此时我们假设$la<lb$,The relevant operations have been done in the code,This is just for convenience）

We need to see if the equation has a solution,formula substructure and 裴蜀定理比较像,拿出来进行对比.

裴蜀定理 ： 存在整数 $x,y$,满足$a\ast x+b\ast y=gcd(a,b)$

This formula is carried out$y$The sign becomes positive,表示$y$是整数,则 $x\ast ta+y\ast tb=lb-la$

我们令$d=gcd(ta,tb)$

Then you can find out if$d|(lb-la)$,Then the formula has a solution,Left endpoints can be coincident.

But what if the left endpoints cannot coincide,Get as close as possible.

Don't forget the right side of the formula at this point$lb-la$代表的是什么,是 区间aThe distance the left endpoint is moved,那么因为$x\ast ta+y\ast tb=d$solution exists,则区间aThe distance moved can be further changed$d$ .

注意：I'm talking about the intervala可以移动,It means that a certain state must exist,The distance between the upper and lower two people has changed in two intervals,It's called interval movement and it's easier to understand.如

$ta=3,[1,4]->[4,7]->[7,10]->[10,13]$

$tb=4,[3,5]->[7,9]->[11,13]$

$[1,4][3,5]$The left endpoint differs$2$,This is an interval state,通过移动,Another interval state occurs$[10,13][11,13]$The left endpoint differs$1$.Moved a step（$d=gcd(3,4)=1$）

The left endpoints are approached as close as possible without overlapping.

There are two states that may be appropriate.

$dis$代表aThe left endpoint of the interval and bThe minimum distance between the left endpoints of the interval（aI think the left endpoint of the interval is less than or equal tob区间左端点）,即$dis=(lb-la)\%d$

• 区间aMove the left endpoint to and intervalbThe left endpoint differs$(lb-la)\%d$,Possibly the closest

  • $min(rb-lb+1,ra-la+1-dis)$

• Then the above situation moves a step back,即区间aThe left endpoint exceeds the intervalb左端点$d-(lb-la)$

  • $dis=d-dis$
  • $min(ra-la+1,rb-lb+1-dis)$

Please draw the two calculations to understand the calculation method.

计算：The case where the left endpoints are coincident can be combined in the code where the left endpoints can be combined,That is, left endpoint merge is a special case of left endpoint not merged.

代码

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int N = 1e5 + 5, mod = 1e9 + 7;

// [l[a] + k * ta, r[a] + k * ta]
// 3 [1, 4] [4, 7] [7, 10] [10, 13] [13, 16] ---
// 4 [3, 5] [7, 9] [11, 13] [15, 17] ---
// The starting point is as the same as possible
// 裴蜀定理：存在x,y 使 ax + by = gcd(a, b)
// la + x * ta = lb + y * tb
// x * ta - y * tb = lb - la
// gcd(ta, tb) | (lb - la)有解
// d = gcd(ta, tb) Seen as the relative moving distance
// la -> la + d -> la + k * d lb
// 差 = lb - la 
// dis = (lb - la) % d

void solve()
{
    
	int la, ra, ta, lb, rb, tb;
	cin >> la >> ra >> ta >> lb >> rb >> tb;
	if(la > lb)
	{
    
		swap(la, lb);
		swap(ra, rb);
		swap(ta, tb);
	}
	int d = __gcd(ta, tb);
	int dis = (lb - la) % d; // Difference of left endpoint
	int ans = 0;
	ans = max(ans, min(rb - lb + 1, ra - la + 1 - dis));
	dis = d - dis; // 向右移动一步
	ans = max(ans, min(ra - la + 1, rb - lb + 1 - dis));
	cout << ans << "\n";
}
int main()
{
    
	ios::sync_with_stdio(false);
	cin.tie(0);

	int t;
	// cin >> t;
	t = 1;
	while(t--)
		solve();
	return 0;
}