Nayeemzaman

Untitled

Feb 24th, 2020
235
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.16 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const long long MAX_SIZE = 1000001;
  4.  
  5. vector<long long >isprime(MAX_SIZE, true);
  6. vector<long long >prime;
  7. vector<long long >SPF(MAX_SIZE);
  8.  
  9. void manipulated_seive(int N)
  10. {
  11.     isprime[0] = isprime[1] = false ;
  12.  
  13.     for (long long int i=2; i<N ; i++)
  14.     {
  15.         if (isprime[i])
  16.         {
  17.             prime.push_back(i);
  18.  
  19.             SPF[i] = i;
  20.         }
  21.         for (long long int j=0;
  22.                 j < (int)prime.size() &&
  23.                 i*prime[j] < N && prime[j] <= SPF[i];
  24.                 j++)
  25.         {
  26.             isprime[i*prime[j]]=false;
  27.  
  28.             SPF[i*prime[j]] = prime[j] ;
  29.         }
  30.     }
  31. }
  32.  
  33. int main()
  34. {
  35.  
  36.     int m;
  37.     double a,b;
  38.     while(cin>>m>>a>>b)
  39.     {
  40.         if(m==0&&a==0&&b==0)
  41.             return 0;
  42.         manipulated_seive((m+1)/2 +1);
  43.         //cout<<prime.size()<<endl;
  44.         double range=a/b;
  45.         //cout<<range<<endl;
  46.         int maxans=0;
  47.         int p1,p2;
  48.         for(int i=prime.size()-1; i>=0; i--)
  49.         {
  50.             int hi=i,lo=0;
  51.             int x=prime[i];
  52.             //cout<<x<<endl;
  53.             int mid;
  54.             double r;
  55.             int f=0;
  56.             while(lo<=hi){
  57.                 mid=(hi+lo)/2;
  58.                 r=prime[mid]/(double)x;
  59.                 //cout<<r<<endl;
  60.                 if(r<range){
  61.                     if(x*prime[mid]>m){
  62.                         f=1;
  63.                         break;
  64.                     }
  65.                     else{
  66.                         lo=mid+1;
  67.                     }
  68.                 }
  69.                 else{
  70.                     if(x*prime[mid]>m)
  71.                         hi=mid-1;
  72.                     else
  73.                         lo=mid+1;
  74.                 }
  75.  
  76.             }
  77.             if(!f){
  78.                 int ans=x*prime[hi];
  79.                 double d=(double)prime[hi]/x;
  80.                 if(ans>maxans&&ans<=m&&d>=range){
  81.                     maxans=ans;
  82.                     p1=x;
  83.                     p2=prime[hi];
  84.                 }
  85.             }
  86.             //cout<<endl;
  87.         }
  88.         cout<<p2<< ' '<<p1<<endl;
  89.         prime.clear();
  90.     }
  91.     return 0;
  92. }
Advertisement
Add Comment
Please, Sign In to add comment