fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long int ll;
  4.  
  5. vector<int> primeSieve(10000, 1);
  6.  
  7. ll power(ll a, ll b){
  8.     if(b==0){
  9.         return 1;
  10.     }
  11.     else if(b%2==0){
  12.         return power(a*a, b/2);
  13.     }
  14.     else{
  15.         return a*power(a, b-1);
  16.     }
  17. }
  18.  
  19.  
  20. void fillSieve(){
  21.     for(int i=2; i<=10000; i+=2){
  22.         primeSieve[i]=2;
  23.     }
  24.     for(int i=3; i<=sqrt(10000); i+=2){
  25.         if(primeSieve[i]==1){
  26.             primeSieve[i]=i;
  27.             for(int j=i; j*i<10000; j++){
  28.                 if(primeSieve[i*j]==1){
  29.                     primeSieve[i*j]=i;
  30.                 }
  31.             }
  32.         }
  33.     }
  34. }
  35.  
  36. int main(){
  37.     ios_base::sync_with_stdio(0);
  38.     cin.tie(NULL);
  39.     cout.tie(NULL);
  40.     int t;
  41.     cin>>t;
  42.     fillSieve();
  43.     while(t--){
  44.         int n, m;
  45.         cin>>n>>m;
  46.         unordered_map<int, int> finalSeq;
  47.         for(int i=0; i<n; i++){
  48.             unordered_map<int, int > mapp;
  49.             int x;
  50.             cin>>x;
  51.             while(x!=1){
  52.                 mapp[primeSieve[x]]++;
  53.                 x/=primeSieve[x];
  54.             }
  55.             for(auto it : mapp){
  56.                 if(it.second > finalSeq[it.first]){
  57.                     finalSeq[it.first]=it.second;
  58.                 }
  59.             }
  60.         }
  61.         int ans=1;
  62.         int ansIncrement=1;
  63.         for(int i=1; i<=m; i++){
  64.             unordered_map<int, int> temp;
  65.             int local=1;
  66.             int x = i;
  67.             while(x!=1){
  68.                 temp[primeSieve[x]]++;
  69.                 x/=primeSieve[x];
  70.             }
  71.             for(auto it : temp){
  72.                 if(it.second>finalSeq[it.first]){
  73.                     ll tem = power(it.first,it.second - finalSeq[it.first]);
  74.                     if(tem>local){
  75.                         local = tem;
  76.                     }
  77.                 }
  78.                 if(local>ansIncrement){
  79.                     ansIncrement=local;
  80.                     ans=i;
  81.                 }
  82.             }
  83.         }
  84.         cout<<ans<<endl;
  85.     }
  86.     return 0;
  87. }
Success #stdin #stdout 0s 4244KB
comments (?)
stdin
copy 
2
3 2
2 1 2
4 7
2 5 6 3
stdout
copy 
1
7
https://ideone.com/XlHuDM
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!