Advertisement
Guest User

Untitled

a guest
Aug 19th, 2017
75
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.78 KB | None | 0 0
  1. #define _CRT_SECURE_NO_DEPRECATE
  2. #include <stdio.h>
  3. #include <iostream>
  4. #include <string>
  5. #include <string.h>
  6. #include <vector>
  7. #include <set>
  8. #include <map>
  9. #include <memory.h>
  10. #include <algorithm>
  11. #include <math.h>
  12. #include <queue>
  13. using namespace std;
  14. typedef long long li;
  15. typedef long double ld;
  16. #define mp make_pair
  17. #define pb push_back
  18. typedef pair <long long, long long> pi;
  19. typedef vector <int> vi;
  20. void solve (li t);
  21. int main ()
  22. {
  23.     #define int li
  24. #ifdef _DEBUG
  25.         freopen ("in.txt", "r", stdin);
  26.         freopen ("out.txt", "w", stdout);
  27. #endif
  28.         int t;
  29.         cin>>t;
  30.         int u=t;
  31.         while (t--)
  32.         solve (u-t);
  33.         return 0;
  34. }
  35. #define int li
  36. int loga ( li q )
  37. {
  38.     li s=1;
  39.     for (int i=0; ; i++)
  40.     {
  41.         if ( q>=s && q<s*10)
  42.             return i;
  43.         s*=10;
  44.     }
  45. }
  46. li n, l, h;
  47. li gcd ( li q, li w )
  48. {
  49.     if ( q<w )
  50.         swap (q, w);
  51.     while (w>0)
  52.     {
  53.         q%=w;
  54.         swap (q, w);
  55.     }
  56.     return q;
  57. }
  58. li NOK ( li q, li w )
  59. {
  60.     li u=w/gcd(q, w);
  61.     if ( loga(u)+loga(q)>17 )
  62.         return h+1;
  63.     return q*(w/gcd(q, w));
  64. }
  65. void solve (int t)
  66. {
  67.     cin>>n>>l>>h;
  68.     int a[10050];
  69.     for ( int i=0; i<n; i++ )
  70.         cin>>a[i];
  71.     int nok[10050];
  72.     int nod[10050];
  73.     bool may[10050];
  74.     memset (may, true, sizeof (may));
  75.     sort (a, a+n);
  76.     n=(unique (a, a+n)-a);
  77.     nok[0]=a[0];
  78.     nod[n-1]=a[n-1];
  79.     for ( int i=1; i<n; i++ )
  80.     {
  81.         nok[i]=NOK (nok[i-1], a[i]);
  82.         if ( nok[i]>h )
  83.             may[i]=false;
  84.     }
  85.     for ( int i=n-2; i>=0; i-- )
  86.         nod[i]=gcd ( nod[i+1], a[i] );
  87.     cout<<"Case #"<<t<<": ";
  88.     vector <int> d;
  89.     for ( int i=1; i*i<=nod[0]; i++ )
  90.         if ( nod[0]%i==0 )
  91.         {
  92.             d.pb(i);
  93.             if (i*i!=nod[0])
  94.             {
  95.                 d.pb(n/i);
  96.             }
  97.             sort (d.begin(), d.end());
  98.             for ( int i=0; i<d.size(); i++ )
  99.                 if ( d[i]<=h && d[i]>=l )
  100.                 {
  101.                     cout<<d[i]<<endl;
  102.                     return;
  103.                 }
  104.         }
  105.     for ( int i=1; i<n; i++ )
  106.     {
  107.         if ( !may[i-1] )
  108.             break;
  109.         if ( may[i-1] && nod[i]%nok[i-1]==0 )
  110.         {
  111.             int r=nod[i]/nok[i-1];
  112.             if ( nok[i-1]>=l && nok[i-1]<=h )
  113.             {
  114.                 cout<<nok[i-1]<<endl;
  115.                 return;
  116.             }
  117.             if ( nok[i-1]>h )
  118.                 continue;
  119.             if (nod[i]<l)
  120.                 continue;
  121.             int ll=l/nok[i-1], rr=h/nok[i-1];
  122.             vector <int> d;
  123.             for ( int j=max (1LL, ll); j*j<=r && j<=rr; j++ )
  124.             {
  125.                 if ( r%j==0 )
  126.                 {
  127.                     d.pb(j);
  128.                     if ( j*j!=r )
  129.                     d.pb (r/j);
  130.                 }
  131.             }
  132.             sort (d.begin(), d.end());
  133.             for ( int j=0; j<d.size(); j++ )
  134.             {
  135.                 int cur=nok[i-1]*d[j];
  136.                 if ( cur<=h && cur>=l )
  137.                 {
  138.                     cout<<cur<<endl;
  139.                     //cout<<"!\n";
  140.                     return;
  141.                 }
  142.                 if ( cur>h )
  143.                     break;
  144.             }
  145.         }
  146.     }
  147.     if ( may[n-1] )
  148.     {
  149.         int cur=nok[n-1];
  150.         if ( cur>=l && cur<=h )
  151.         {
  152.             cout<<cur<<endl;
  153.             return;
  154.         }
  155.         if ( cur<l )
  156.         {
  157.             int ll=l/cur, rr=h/cur;
  158.             if ( ll!=rr )
  159.             {
  160.                 cout<<cur*(ll+1)<<endl;
  161.                 return;
  162.             }
  163.         }
  164.     }
  165.     cout<<"NO"<<endl;
  166. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement