fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <cstdio>
  5.  
  6. using namespace std;
  7.  
  8. #define ll long long
  9. #define FAST ios_base::sync_with_stdio(false); cin.tie(NULL);
  10. #define FILE if (fopen("perfect.inp", "r")) { freopen("perfect.inp", "r", stdin); freopen("perfect.out", "w", stdout); }
  11. #define int long long
  12. #define pb push_back
  13.  
  14. const int M = 100005;
  15. const int K = 1000005;
  16. int n;
  17. int a[2 * M];
  18. int p[K];
  19. int d[K];
  20. int l[K];
  21.  
  22. void s() {
  23.     for (int i = 2; i < K; ++i) {
  24.         if (p[i] == 0) {
  25.             for (int j = i; j < K; j += i) {
  26.                 if (p[j] == 0) p[j] = i;
  27.             }
  28.         }
  29.     }
  30. }
  31.  
  32. vector<int> g(int x) {
  33.     vector<int> r;
  34.     while (x > 1) {
  35.         int f = p[x];
  36.         r.pb(f);
  37.         while (x % f == 0) x /= f;
  38.     }
  39.     return r;
  40. }
  41.  
  42. signed main() {
  43.     FAST;
  44.     FILE;
  45.  
  46.     s();
  47.  
  48.     if (!(cin >> n)) return 0;
  49.  
  50.     for (int i = 1; i <= n; ++i) {
  51.         cin >> a[i];
  52.     }
  53.  
  54.     int m = 0;
  55.     int w = 0;
  56.  
  57.     for (int i = 1; i <= n; ++i) {
  58.         vector<int> v = g(a[i]);
  59.         for (int x : v) {
  60.             if (l[x] == i - 1) {
  61.                 d[x]++;
  62.             } else {
  63.                 d[x] = 1;
  64.             }
  65.             l[x] = i;
  66.             m = max(m, d[x]);
  67.         }
  68.     }
  69.  
  70.     if (m == 0) {
  71.         cout << "0 0\n";
  72.         return 0;
  73.     }
  74.  
  75.     for (int i = 0; i < K; ++i) {
  76.         d[i] = 0;
  77.         l[i] = 0;
  78.     }
  79.  
  80.     for (int i = 1; i <= n; ++i) {
  81.         vector<int> v = g(a[i]);
  82.         for (int x : v) {
  83.             if (l[x] == i - 1) {
  84.                 d[x]++;
  85.             } else {
  86.                 d[x] = 1;
  87.             }
  88.             l[x] = i;
  89.  
  90.             if (d[x] == m) {
  91.                 w++;
  92.             }
  93.         }
  94.     }
  95.  
  96.     cout << m << " " << w << "\n";
  97.  
  98.     return 0;
  99. }
  100.  
Success #stdin #stdout 0.02s 27076KB
comments (?)
stdin
copy 
10
4 5 9 7 1 3 2 6 8 10
stdout
copy 
4 1
https://ideone.com/RWzVDy
language:
C++ (gcc 8.3)
created:
1 day 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!