Mail.Ru Cup 2018 Round 2 C. Lucky Days（拓展欧几里得）

待参考资料：

　　[1]:https://www.cnblogs.com/Patt/p/9941200.html

•题意

　　a君，b君存在幸运周期；

　　a君在第[ L₁+k·t₁,R₁+k·t₁]天为幸运天；

　　b君在第[ L₂+k·t₂,R₂+k·t₂]天为幸运天；

　　求 a君，b君同为幸运天数的最大的连续天数；

•题解

　　a君所有幸运天数开始的时刻为 L_a = L₁+x·t₁；

　　b君所有幸运天数开始的时刻为 L_b = L₂+y·t₂；

　　假设 a君每个周期幸运的天数为 len_a , b君的为 len_b；

　　①如果 ∃ x,y 使得 L_a = L_b ，那么答案就是 min(len_a,len_b)；

　　②反之，根据贪心策略，两者的幸运天数开始越接近，那么两者的公共幸运天数就越多；

　　　也就是说，找到最小的非负整数 d₁ 使得 L_a + d₁ = L_b 或最小的非负整数 d₂ 使得 L_a = L_b+d₂；

　　如何判断①是否成立呢？

　　　　根据拓展欧几里得，使得①成立当且仅当 GCD(t₁,t₂) | |L_b-L_a|；

　　如果不成立，如何找到最小的d₁,d₂呢？

　　

　　由 ①② 可得 b1 = (L₂-L₁)%GCD(t₁,t₂)，并且要确保 b₁ > 0;

　　同理可求b₂；

•Code

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define GCD(a,b) __gcd(a,b)
 4 #define ll long long
 5 
 6 ll l1,r1,t1;
 7 ll l2,r2,t2;
 8 
 9 ll Solve()
10 {
11     if(abs(l2-l1)%GCD(t1,t2) == 0)
12         return min(r1-l1+1,r2-l2+1);
13 
14     ll d1=(l2-l1)%GCD(t1,t2);
15     if(d1 < 0)
16         d1 += GCD(t1,t2);
17 
18     ll d2=(l1-l2)%GCD(t1,t2);
19     if(d2 < 0)
20         d2 += GCD(t1,t2);
21 
22     ///两者幸运天数无交集时，取min时会返回负数，所以需要对0取个max
23     return max(1ll*0,max(min(r1-l1-d1+1,r2-l2+1),min(r1-l1+1,r2-l2-d2+1)));
24 }
25 int main()
26 {
27     scanf("%lld%lld%lld",&l1,&r1,&t1);
28     scanf("%lld%lld%lld",&l2,&r2,&t2);
29     printf("%lld
",Solve());
30 
31     return 0;
32 }

View Code