Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define _CRT_SECURE_NO_DEPRECATE
- #include <stdio.h>
- #include <iostream>
- #include <string>
- #include <string.h>
- #include <vector>
- #include <set>
- #include <map>
- #include <memory.h>
- #include <algorithm>
- #include <math.h>
- #include <queue>
- using namespace std;
- typedef long long li;
- typedef long double ld;
- #define mp make_pair
- #define pb push_back
- typedef pair <long long, long long> pi;
- typedef vector <int> vi;
- void solve (li t);
- int main ()
- {
- #define int li
- #ifdef _DEBUG
- freopen ("in.txt", "r", stdin);
- freopen ("out.txt", "w", stdout);
- #endif
- int t;
- cin>>t;
- int u=t;
- while (t--)
- solve (u-t);
- return 0;
- }
- #define int li
- int loga ( li q )
- {
- li s=1;
- for (int i=0; ; i++)
- {
- if ( q>=s && q<s*10)
- return i;
- s*=10;
- }
- }
- li n, l, h;
- li gcd ( li q, li w )
- {
- if ( q<w )
- swap (q, w);
- while (w>0)
- {
- q%=w;
- swap (q, w);
- }
- return q;
- }
- li NOK ( li q, li w )
- {
- li u=w/gcd(q, w);
- if ( loga(u)+loga(q)>17 )
- return h+1;
- return q*(w/gcd(q, w));
- }
- void solve (int t)
- {
- cin>>n>>l>>h;
- int a[10050];
- for ( int i=0; i<n; i++ )
- cin>>a[i];
- int nok[10050];
- int nod[10050];
- bool may[10050];
- memset (may, true, sizeof (may));
- sort (a, a+n);
- n=(unique (a, a+n)-a);
- nok[0]=a[0];
- nod[n-1]=a[n-1];
- for ( int i=1; i<n; i++ )
- {
- nok[i]=NOK (nok[i-1], a[i]);
- if ( nok[i]>h )
- may[i]=false;
- }
- for ( int i=n-2; i>=0; i-- )
- nod[i]=gcd ( nod[i+1], a[i] );
- cout<<"Case #"<<t<<": ";
- vector <int> d;
- for ( int i=1; i*i<=nod[0]; i++ )
- if ( nod[0]%i==0 )
- {
- d.pb(i);
- if (i*i!=nod[0])
- {
- d.pb(n/i);
- }
- sort (d.begin(), d.end());
- for ( int i=0; i<d.size(); i++ )
- if ( d[i]<=h && d[i]>=l )
- {
- cout<<d[i]<<endl;
- return;
- }
- }
- for ( int i=1; i<n; i++ )
- {
- if ( !may[i-1] )
- break;
- if ( may[i-1] && nod[i]%nok[i-1]==0 )
- {
- int r=nod[i]/nok[i-1];
- if ( nok[i-1]>=l && nok[i-1]<=h )
- {
- cout<<nok[i-1]<<endl;
- return;
- }
- if ( nok[i-1]>h )
- continue;
- if (nod[i]<l)
- continue;
- int ll=l/nok[i-1], rr=h/nok[i-1];
- vector <int> d;
- for ( int j=max (1LL, ll); j*j<=r && j<=rr; j++ )
- {
- if ( r%j==0 )
- {
- d.pb(j);
- if ( j*j!=r )
- d.pb (r/j);
- }
- }
- sort (d.begin(), d.end());
- for ( int j=0; j<d.size(); j++ )
- {
- int cur=nok[i-1]*d[j];
- if ( cur<=h && cur>=l )
- {
- cout<<cur<<endl;
- //cout<<"!\n";
- return;
- }
- if ( cur>h )
- break;
- }
- }
- }
- if ( may[n-1] )
- {
- int cur=nok[n-1];
- if ( cur>=l && cur<=h )
- {
- cout<<cur<<endl;
- return;
- }
- if ( cur<l )
- {
- int ll=l/cur, rr=h/cur;
- if ( ll!=rr )
- {
- cout<<cur*(ll+1)<<endl;
- return;
- }
- }
- }
- cout<<"NO"<<endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement