fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define fast_io ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
  4. #define int long long
  5.  
  6. int32_t main() {
  7.     fast_io;
  8.     int t; cin >> t;
  9.     while (t--) {
  10.         int n; cin >> n;
  11.         string s; cin >> s;
  12.         bool all1 = true;
  13.         for (char c: s) if (c == '0') { all1 = false; break; }
  14.         if (all1) {
  15.             cout << 0 << '\n';
  16.             continue;
  17.         }
  18.         vector<int> divisors;
  19.         for (int d = 1; d * d <= n; ++d) {
  20.             if (n % d == 0) {
  21.                 divisors.push_back(d);
  22.                 if (d * d != n) divisors.push_back(n / d);
  23.             }
  24.         }
  25.         sort(divisors.begin(), divisors.end());
  26.         int ans = INT_MAX;
  27.         for (int g : divisors) {
  28.             bool ok = true;
  29.             for (int r = 0; r < g && ok; ++r) {
  30.                 bool has1 = false;
  31.                 for (int i = r; i < n; i += g) {
  32.                     if (s[i] == '1') { has1 = true; break; }
  33.                 }
  34.                 if (!has1) ok = false;
  35.             }
  36.             if (ok) ans = min(ans, g);
  37.         }
  38.         if (ans == INT_MAX) ans = n;
  39.         cout << ans << '\n';
  40.     }
  41.     return 0;
  42. }
  43.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
5
1
1
3
101
4
0110
11
10101010100
2
11
stdout
copy 
0
1
1
1
0
https://ideone.com/XIJbCR
language:
C++ (gcc 8.3)
created:
2 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!