Help analyzing Randomize Algorithms


F. GCD Groups 2

What I do understood

The basic idea about what we are doing in below logic (no more than k=9 primes, kill primes etc.).

What I don’t understand (Analysis Part)

How in this and similar algorithms we find #iterations such that we can pass all the tests or probability of failure is very small (also what is considered small here).

What I tried so far

Read several blogs, comments related to randomize algorithms, expected value and so on & came back to analyze this multiple times.



Code (Partially similar to editorial with same base idea)

#include <bits/stdc++.h>

using namespace std;

int main() {
  int n;
  scanf("%d", &n);
  vector<int> a(n);
  for (int &ai : a) { scanf("%d", &ai); }
  vector<int> p(n), grp(n);
  iota(p.begin(), p.end(), 0);
  for (int t=0; t < 45; t++) {
    random_shuffle(p.begin(), p.end());
    int g1=0, g2=0;
    for (int pi : p) {
      if (gcd(g1, a[pi]) != g1) {
        g1 = gcd(g1, a[pi]);
      } else {
        g2 = gcd(g2, a[pi]);
    if (g1 == 1 and g2 == 1) {
      for (int gi : grp) { printf("%d ", gi); }
      return 0;