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

 #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 ;

 }

巴特西

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

•题意

•题解

•Code

最新文章

热门文章