Advertisement
Guest User

Untitled

a guest
Aug 19th, 2017
606
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.73 KB | None | 0 0
  1. /**
  2.  * Author: Sergey Kopeliovich (Burunduk30@gmail.com)
  3.  */
  4.  
  5. #include <ctime>
  6. #include <cmath>
  7. #include <cctype>
  8. #include <cstdio>
  9. #include <cstdlib>
  10. #include <cstring>
  11. #include <cassert>
  12.  
  13. #include <algorithm>
  14. #include <vector>
  15. #include <string>
  16. #include <sstream>
  17. #include <iostream>
  18. #include <functional>
  19. #include <map>
  20. #include <set>
  21. #include <fstream>
  22.  
  23. using namespace std;
  24.  
  25. #ifdef _WIN32
  26. #  define I64 "%I64d"
  27. #else
  28. #  define I64 "%Ld"
  29. #endif
  30.  
  31. #define forn(i, n) for (int i = 0; i < (int)(n); i++)
  32. #define fornd(i, n) for (int i = (int)(n) - 1; i >= 0; i--)
  33. #define forab(i, a, b) for (int i = (int)(a); i <= (int)(b); i++)
  34. #define forabd(i, a, b) for (int i = (int)(b); i >= (int)(a); i--)
  35. #define forit(i, a) for (__typeof((a).begin()) i = (a).begin(); i != (a).end(); i++)
  36. #define sz(a) (int)(a).size()
  37. #define all(a) (a).begin(), (a).end()
  38. #define zero(a) memset(a, 0, sizeof(a))
  39. #define pb push_back
  40. #define mp make_pair
  41.  
  42. #define EOL(i, n) " \n"[i == (n) - 1]
  43. #define LEN(a) (int)(sizeof(a) / sizeof(a[0]))
  44. #define IS(a, i) (((a) >> (i)) & 1)
  45.  
  46. typedef double dbl;
  47. typedef long long ll;
  48. typedef vector <int> vi;
  49. typedef pair <int, int> pii;
  50.  
  51. template <class T> T inline sqr(T x) { return x * x; }
  52. template <class T> inline void relaxMin( T &a, T b ) { a = min(a, b); }
  53. template <class T> inline void relaxMax( T &a, T b ) { a = max(a, b); }
  54.  
  55. string str( int i ) { char s[100]; sprintf(s, "%d", i); return string(s); }
  56.  
  57. inline int sign( int x ) { return x > 0 ? 1 : (x < 0 ? -1 : 0); }
  58. inline int myAbs( int a ) { return a > 0 ? a : -a; }
  59.  
  60. const int maxN = (int)1e4 + 10;
  61. const ll inf = (ll)1e18;
  62. const int maxX = (int)1e8 + 100;
  63. const int maxP = (int)6e6;
  64.  
  65. unsigned char is[maxX / 8 + 1];
  66. int pn = 0, p[maxP];
  67.  
  68. int N;
  69. ll L, H, a[maxN], g[maxN], lcm[maxN];
  70.  
  71. int xn;
  72. ll x[99];
  73. int k[99];
  74.  
  75. vector <ll> D;
  76.  
  77. void go( ll val, int i )
  78. {
  79.   if (i == xn)
  80.   {
  81.     D.pb(val);
  82.     return;
  83.   }
  84.   for (int j = 0; j <= k[i]; j++)
  85.     go(val, i + 1), val *= x[i];
  86. }
  87.  
  88. void getD( ll X )
  89. {
  90.   D.clear();
  91.   xn = 0;
  92.   for (int i = 0; i < pn && (ll)p[i] * p[i] <= X; i++)
  93.     if (X % p[i] == 0)
  94.     {
  95.       k[xn] = 0, x[xn] = p[i];
  96.       while (X % p[i] == 0)
  97.         k[xn]++, X /= p[i];
  98.       xn++;
  99.     }
  100.   if (X > 1)
  101.     k[xn] = 1, x[xn++] = X;
  102.   go(1, 0);
  103. }
  104.  
  105. int main()
  106. {
  107.   for (int i = 2; i * i < maxX; i++)
  108.     if (!IS(is[i >> 3], i & 7))
  109.       for (int j = i * i; j < maxX; j += i)
  110.         is[j >> 3] |= 1 << (j & 7);
  111.   for (int i = 2; i < maxX; i++)
  112.     if (!IS(is[i >> 3], i & 7))
  113.       p[pn++] = i;
  114.  
  115.   int tn;
  116.   scanf("%d", &tn);
  117.   forab(tt, 1, tn)
  118.   {
  119.     fprintf(stderr, "%d\n", tt);
  120.     scanf("%d%I64d%I64d", &N, &L, &H);
  121.     forn(i, N)
  122.       scanf("%I64d", &a[i]);
  123.     sort(a, a + N);
  124.     g[N - 1] = a[N - 1];
  125.     for (int i = N - 2; i >= 0; i--)
  126.       g[i] = __gcd(a[i], g[i + 1]);
  127.     lcm[0] = 1;
  128.     forn(i, N)
  129.     {
  130.       ll x = lcm[i], y = a[i] / __gcd(a[i], lcm[i]);
  131.       if (x >= inf / y)
  132.         lcm[i + 1] = inf;
  133.       else
  134.         lcm[i + 1] =  x * y;
  135.     }
  136.  
  137.     int good = 0;
  138.     forn(i, N)
  139.       if (lcm[i] <= g[i] && g[i] % lcm[i] == 0)
  140.       {
  141.         getD(g[i] / lcm[i]);
  142.         sort(all(D));
  143.         forn(j, sz(D))
  144.         {
  145.           ll x = lcm[i] * D[j];
  146.           if (L <= x && x <= H)
  147.           {
  148.             printf("Case #%d: %I64d\n", tt, x);
  149.             good = 1;
  150.             break;
  151.           }
  152.         }
  153.         if (good)
  154.           break;
  155.       }
  156.     if (!good)
  157.       if (lcm[N] <= H)
  158.       {
  159.         ll x = lcm[N] * ((L + lcm[N] - 1) / lcm[N]);
  160.         if (x <= H)
  161.         {
  162.           printf("Case #%d: %I64d\n", tt, x);
  163.           good = 1;
  164.         }
  165.       }
  166.     if (!good)
  167.       printf("Case #%d: NO\n", tt);
  168.   }
  169.   return 0;
  170. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement