待参考资料:
[1]:https://www.cnblogs.com/Patt/p/9941200.html
•题意
a君,b君存在幸运周期;
a君在第[ L1+k·t1,R1+k·t1]天为幸运天;
b君在第[ L2+k·t2,R2+k·t2]天为幸运天;
求 a君,b君 同为幸运天数的最大的连续天数;
•题解
a君所有幸运天数开始的时刻为 La = L1+x·t1;
b君所有幸运天数开始的时刻为 Lb = L2+y·t2;
假设 a君 每个周期幸运的天数为 lena , b君的为 lenb;
①如果 ∃ x,y 使得 La = Lb ,那么答案就是 min(lena,lenb);
②反之,根据贪心策略,两者的幸运天数开始越接近,那么两者的公共幸运天数就越多;
也就是说,找到最小的非负整数 d1 使得 La + d1 = Lb 或最小的非负整数 d2 使得 La = Lb+d2;
如何判断①是否成立呢?
根据拓展欧几里得,使得①成立当且仅当 GCD(t1,t2) | |Lb-La|;
如果不成立,如何找到最小的d1,d2呢?
由 ①② 可得 b1 = (L2-L1)%GCD(t1,t2),并且要确保 b1 > 0;
同理可求b2;
•Code
#include<bits/stdc++.h>
using namespace std;
#define GCD(a,b) __gcd(a,b)
#define ll long long ll l1,r1,t1;
ll l2,r2,t2; ll Solve()
{
if(abs(l2-l1)%GCD(t1,t2) == )
return min(r1-l1+,r2-l2+); ll d1=(l2-l1)%GCD(t1,t2);
if(d1 < )
d1 += GCD(t1,t2); ll d2=(l1-l2)%GCD(t1,t2);
if(d2 < )
d2 += GCD(t1,t2); ///两者幸运天数无交集时,取min时会返回负数,所以需要对0取个max
return max(1ll*,max(min(r1-l1-d1+,r2-l2+),min(r1-l1+,r2-l2-d2+)));
}
int main()
{
scanf("%lld%lld%lld",&l1,&r1,&t1);
scanf("%lld%lld%lld",&l2,&r2,&t2);
printf("%lld\n",Solve()); return ;
}