fork download
copy 
  1. /*
  2.     author: Tran Van Nam
  3.     Nguyen Trai High School - Quang Binh
  4. */
  5. #include <bits/stdc++.h>
  6. using namespace std;
  7.  
  8. const int N = 1e7 + 5;;
  9. const int INF = 1e9;
  10.  
  11. int a[N], phi[N];
  12.  
  13. signed main(){
  14.     ios_base::sync_with_stdio(0);
  15.     cin.tie(0); cout.tie(0);
  16.  
  17.     // freopen("SUBARR.INP", "r", stdin);
  18.     // freopen("SUBARR.OUT", "w", stdout);
  19.  
  20.     for (int i = 1; i < N; i++) phi[i] = i;
  21.     for (int i = 2; i*i < N; i++)
  22.         if (phi[i] == i)
  23.             for (int j = i; i*j < N; j++) phi[i*j] = i;
  24.  
  25.     int n, k; cin >> n >> k;
  26.     for (int i = 1; i <= n; i++){
  27.         int x; cin >> x;
  28.         a[i] = 1;
  29.         while (x > 1){
  30.             int divisor = phi[x];
  31.             int cnt = 0;
  32.             while (x % divisor == 0){
  33.                 cnt++;
  34.                 x /= divisor;
  35.             }
  36.             a[i] *= (cnt + 1);
  37.         }
  38.     }
  39.  
  40.     int d = 0;
  41.     for (int i = 1; i <= n; i++) d = max(d, a[i]);
  42.  
  43.     int ans = INF, sum = 0;
  44.     for (int l = 1, r = 1; r <= n; r++){
  45.         sum += (a[r] == d);
  46.         while (sum >= k){
  47.             ans = min(ans, r - l + 1);
  48.             sum -= (a[l] == d);
  49.             l++;
  50.         }
  51.     }
  52.  
  53.     if (ans == INF) cout << -1; else cout << ans;
  54.  
  55.     return 0^0;
  56. }
Success #stdin #stdout 0.22s 61252KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-5800136
https://ideone.com/HoUAmP
language:
C++14 (clang 8.0)
created:
264 days 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!