Advertisement
agmike

B. Друзья и подарки

Oct 24th, 2014
161
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C# 1.47 KB | None | 0 0
  1. using System;
  2. using System.Collections.Generic;
  3. using System.Globalization;
  4. using System.Linq;
  5. using System.Text;
  6. using System.Numerics;
  7.  
  8.  
  9. public static class solver
  10. {
  11.     static long Gcd(long a, long b)
  12.     {
  13.         while (b != 0) {
  14.             var rem = a % b;
  15.             a = b;
  16.             b = rem;
  17.         }
  18.         return a;
  19.     }
  20.  
  21.     static long cnt1, cnt2, x, y;
  22.  
  23.     static long CountMatching(long max, long divisor)
  24.     {
  25.         return max / divisor;
  26.     }
  27.  
  28.     static bool Possible(long max)
  29.     {
  30.         var notFor1 = CountMatching(max, x);
  31.         var notFor2 = CountMatching(max, y);
  32.         var notFor12 = CountMatching(max, x * y);
  33.         var for12 = max - CountMatching(max, Gcd(x, y));
  34.  
  35.         var left = (max - notFor1) + (max - notFor2) - for12;
  36.         return left >= (cnt1 + cnt2);
  37.     }
  38.  
  39.  
  40.  
  41.     public static void Main()
  42.     {
  43.         var input = Console.ReadLine().Split(null);
  44.         cnt1 = long.Parse(input[0]);
  45.         cnt2 = long.Parse(input[1]);
  46.         x = long.Parse(input[2]);
  47.         y = long.Parse(input[3]);
  48.  
  49.         var l = 0L;
  50.         var r = long.MaxValue / 2;
  51.  
  52.         while (l < r - 1) {
  53.             var m = (l + r) / 2;
  54.             if (Possible(m))
  55.                 r = m;
  56.             else
  57.                 l = m;
  58.         }
  59.  
  60.         if (Possible(l))
  61.             Console.WriteLine(l);
  62.         else
  63.             Console.WriteLine(r);
  64.  
  65. #if !ONLINE_JUDGE
  66.         Console.ReadLine();
  67. #endif
  68.     }
  69. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement