fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. typedef long long int ll;
  6.  
  7. ll gcd(ll a, ll b) {
  8.     if (b == 0) return a;
  9.     return gcd(b, a % b);
  10. }
  11.  
  12. int main() {
  13.     int t;
  14.     cin >> t;
  15.     while (t--) {
  16.         int n;
  17.         cin >> n;
  18.         vector<int> arr(n);
  19.         for (int i = 0; i < n; i++) cin >> arr[i];
  20.         vector<int> binary(n);
  21.         for (int i = 0; i < n; i++) {
  22.             binary[i] = (gcd(arr[i], arr[(i + 1) % n]) > 1) ? 1 : 0;
  23.         }
  24.  
  25.         vector<int> run_lengths;
  26.         int i = 0;
  27.         while (i < n) {
  28.             if (binary[i] == 1) {
  29.                 int j = i;
  30.                 while (j < n && binary[j] == 1) j++;
  31.                 run_lengths.push_back(j - i);
  32.                 i = j;
  33.             } else {
  34.                 i++;
  35.             }
  36.         }
  37.  
  38.  
  39.         if (binary[0] == 1 && binary[n - 1] == 1) {
  40.  
  41.             int first = 0, last = run_lengths.size() - 1;
  42.  
  43.             int merged = run_lengths[0] + run_lengths.back();
  44.             run_lengths[0] = merged;
  45.             run_lengths.pop_back();
  46.         }
  47.  
  48.     for(int k = 2 ; k<=n;k++){
  49.     int ans = 0 ; 
  50.     for(int l : run_lengths){
  51.     	ans += l/(k-1);
  52.     }
  53.     cout<<ans<<" ";
  54.     }
  55.     }
  56.  
  57.     return 0;
  58. }
  59.  
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
1 8
2 4 6 8 10 1 6 8
stdout
copy 
6 3 2 1 1 1 0
https://ideone.com/mxtt96
language:
C++ (gcc 8.3)
created:
10 days 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!