fork download
copy 
  1. #include <iostream>
  2. #include <stdio.h>
  3. #include <algorithm>
  4. #include <string>
  5. #include <string.h>
  6. #include <map>
  7. #include <set>
  8. #include <vector>
  9. #include <queue>
  10. #include <math.h>
  11. #include <iomanip>
  12. using namespace std;
  13.  
  14. #define name "CANDY"
  15. #define ini freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout)
  16. #define fo(i,a,b) for (int i = a; i <= b; i++)
  17. #define fu(i,a,b) for (int i = a; i >= b; i--)
  18. #define foe(it,c) for (__typeof(c.begin()) it = c.begin(); it != c.end(); it++)
  19. #define ll long long
  20. #define pii pair <int, int>
  21. #define pll pair <ll, ll>
  22. #define db double
  23.  
  24. const int N = 1e6+1;
  25. int a[N], H[N], cnt[N], n;
  26. bool Mark[N];
  27. ll res, sum;
  28. vector <pii> F[N];
  29.  
  30. ll POW(ll x, ll n){
  31.     if (n == 0) return (ll)1;
  32.     if (n == 1) return x;
  33.     ll y = POW(x,n/2);
  34.     y *= y;
  35.     if (n % 2) return x*y;
  36.     else return y;
  37. }
  38.  
  39. void Build(int N){
  40.     for (ll i = 2; i < N; i++){
  41.         if (!Mark[i]){
  42.             ll j = i*i;
  43.             H[i] = i;
  44.             while (j < N){
  45.                 Mark[j] = true;
  46.                 if (!H[j]) H[j] = i;
  47.                 j += i;
  48.             }
  49.         }
  50.     }
  51. }
  52.  
  53. set <int> S;
  54.  
  55. void Solve(int x, int p){
  56.     if (x == 1) return;
  57.     while (x > 1){
  58.         int y = H[x];
  59.         int d = 0;
  60.         while (x % y == 0){
  61.             x /= y;
  62.             cnt[y]++;
  63.             d++;
  64.         }
  65.         F[p].push_back(pii(y,d));
  66.         S.insert(y);
  67.     }
  68. }
  69.  
  70.  
  71. void Process(){
  72.     int r = 0;
  73.     foe(it,S){
  74.         cnt[*it] /= n;
  75.         r += cnt[*it];
  76.     }
  77.     fo(i,1,n){
  78.         int t = r;
  79.         //cout << a[i] << endl;
  80.         foe(it,F[i]){
  81.             int x = it->first;
  82.             int y = it->second;
  83.             //cout << x << ' ' << y << endl;
  84.             if (y >= cnt[x]){
  85.                 t -= cnt[x];
  86.             }
  87.         }
  88.         sum += t;
  89.     }
  90.     res = 1;
  91.     foe(it,S){
  92.         //cout << *it << ' ' << cnt[*it] << endl;
  93.         res *= POW(*it,cnt[*it]);
  94.     }
  95.     cout << res << ' ' << sum;
  96. }
  97.  
  98. int main()
  99. {
  100.     ios_base::sync_with_stdio(false);
  101.     cin.tie(0); cout.tie(0);
  102.     //ini;
  103.     cin >> n;
  104.     int mx = 0;
  105.     fo(i,1,n){
  106.         cin >> a[i];
  107.         mx = max(mx, a[i]);
  108.     }
  109.     Build(mx+1);
  110.     fo(i,1,n){
  111.         Solve(a[i],i);
  112.     }
  113.     Process();
  114. }
  115.  
Success #stdin #stdout 0s 51368KB
comments (?)
stdin
copy 
10
8000 5000 2500 9025 4000 6250 7675 3591 6435 5000
stdout
copy 
100 14
https://ideone.com/8qKfLE
language:
C++14 (gcc 8.3)
created:
5 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!