fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3.  
  4. using namespace std;
  5.  
  6. const int MAX = 1e7;
  7. const int mod = 1e9 + 7;
  8. bool primes_sieve[MAX + 10];
  9. vector <ll> primes;
  10.  
  11.  
  12. ll gcd(ll a, ll b){
  13.     if(b == 0)
  14.         return a;
  15.     return gcd(b, a%b);
  16. }
  17.  
  18. void sieve(){
  19.     memset(primes_sieve, true, MAX + 10);
  20.     for (ll i = 2; i*i <= MAX; i++){
  21.         if(primes_sieve[i]){
  22.             for (ll j = i*i; j <= MAX; j += i)
  23.                     primes_sieve[j] = false;
  24.             primes.push_back(i);
  25.         }
  26.     }
  27. }
  28.  
  29. ll power(ll a, ll b, const int p = mod){
  30.  
  31.     ll result = 1;
  32.     a = a%p;
  33.     while(b)
  34.     {
  35.         if(b & 1)
  36.             result = (a*result)%p;
  37.  
  38.         b = b >> 1;
  39.         a = (a*a)%p;
  40.     }
  41.  
  42.     return result;
  43. }
  44.  
  45. int main()
  46. {   
  47.     sieve();
  48.  
  49.     ll n;
  50.     cin >> n;
  51.     map<ll,ll> mp;
  52.  
  53.     for (ll i = 0; i < n; i++)
  54.     {
  55.         ll m;
  56.         cin >> m;
  57.         ll a[m];
  58.         ll mx = 0;
  59.         for (ll j = 0; j < m; j++)
  60.         {
  61.             cin >> a[j];
  62.             mx = max(mx, a[j]);
  63.         }
  64.         for (auto prime: primes)
  65.         {
  66.             if(prime > mx)
  67.                 break;
  68.             if(mp.count(prime) == 0)
  69.                 mp[prime] = 1e9 + 10;
  70.             ll cnt = 0;
  71.             for (ll j = 0; j < m; j++)
  72.             {
  73.                 if(a[j] < prime)    
  74.                     continue;
  75.                 while(a[j] % prime == 0)
  76.                 {
  77.                     a[j] /= prime;
  78.                     cnt++;
  79.                 }
  80.             }
  81.             mp[prime] = min(mp[prime], cnt);
  82.         }
  83.     }
  84.     ll ans = 1;
  85.     for(auto prime: primes)
  86.     {
  87.         ans *= power(prime, mp[prime]);
  88.         ans %= mod;
  89.     }
  90.  
  91.     cout << ans << endl;
  92. }
  93.  
  94.  
Runtime error #stdin #stdout 0.04s 13140KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/IHo1jt
problem ADAGCD, based on SPOJ submission 27876703 (CPP14), 2021-05-13 06:12:51
language:
C++14 (gcc 8.3)
created:
2 years ago
visibility:
secret

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!