CF - Orac & LCM

Official Editorial

Solution: Prime Factorization

For each prime, the second-to-lowest exponent of the prime that occurs in any of the numbers in the input is the exponent of this prime that will appear in the final answer.

Here's a short solution that accomplishes this without explicitly computing any prime factorizations!

Copy
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

ll a, b;
// a stores minimum exponents (gcd of all numbers seen so far)
// b stores second minimum exponents
int n;

Copy
import java.io.*;
import java.util.*;

public class oraclcm {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());
		int[] nums = new int[N];

Copy
import math

"""
    a stores minimum exponents (gcd of all numbers seen so far)
    b stores second minimum exponents
"""


def red():  # restore invariant mentioned above
	global a, b

If it's hard to understand what exactly this code is doing at first glance, a good first step is to simulating the code in the case where each $a_i$ is a power of the same prime (say, $2^k$). If the algorithm works for this case, then it will also work in the general case since the contributions of different primes are computed independently and multiplied together.

Here's another way of thinking about this:

For a fixed $j$,

and we can update $\gcd_{0\le i<j}(a_i)$ when $j$ increases by one. Taking the GCD of the results for each $j$ gives the answer.