PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: beevo
Tester & Editorialist: iceknight1093
DIFFICULTY:
2739
PREREQUISITES:
Elementary Number Theory, Prime factorization using a sieve
PROBLEM:
You have an array A containing N integers upto 10^7.
Define a sequence of arrays A^{(k)}, where:
- A^{(0)} = A
- A^{(k)} = \frac{L}{G} \cdot A^{(k-1)} for k \geq 1, where G and L are respectively the gcd and lcm of A^{(k-1)}
Answer Q queries; each giving you an integer k and asking you to find the gcd and lcm of A^{(k)}, modulo 10^9 + 7.
EXPLANATION:
Let G_k and L_k denote the gcd and lcm of A^{(k)}.
Let’s first find the answers for K = 0, i.e, G_0 and L_0.
Finding G_0 is trivial by just iterating across the array; however, L_0 can be extremely large — computing it directly it impossible.
However, notice that A_i \leq 10^7 means that even if L_0 is very large, all its prime factors will be \leq 10^7.
This means we can find L_0 in terms of its prime factorization.
Recall that if we have two integers x and y such that
then \text{lcm}(x, y) = p_1^{\max(a_1, b_1)}p_2^{\max(a_2, b_2)}\ldots p_k^{\max(a_k, b_k)}
Of course, this generalizes to the \text{lcm} of more than two integers as well: the power of each prime p_i in the \text{lcm} will be the maximum power of p_i present in one of the numbers.
Using this idea, let’s compute L_0.
Consider some prime p \leq 10^7. To know the power of p in L_0, we want to know the maximum power of p across all A_i.
In particular, we have the following algorithm:
- Let \text{mx}_p denote the maximum power of p present in some A_i.
Initially, \text{mx}_p = 0 for all p. - Then, for each i from 1 to N:
- Find all prime factors of A_i; let them be p_1, p_2, \ldots, p_k with respective powers a_1, a_2, \ldots, a_k.
- For each 1 \leq i \leq k, set \text{mx}_{p_i} \gets \max(\text{mx}_{p_i}, a_i)
At the end of this process, \text{mx}_p will be the value we want, for every p.
For this to run quickly, we need to be able to quickly prime-factorize the A_i values.
This can be done using a slight modification to the sieve of Eratosthenes, storing a prime divisor of each integer instead of just a boolean value.
An overview of this can be seen in this blog.
Any integer x has \leq \log_2 x prime factors (since each prime factor is at least 2), so the entire process above takes \mathcal{O}(N\log 10^7) time.
Once this is done, L_0 is the product of p^{\text{mx}_p} across all primes \leq p.
For k \gt 0, notice that for any integers x, a_1, a_2, \ldots, a_k we have:
- \gcd(x\cdot a_1, x\cdot a_2, \ldots, x\cdot a_k) = x\cdot \gcd(a_1, a_2, \ldots, a_k)
- \text{lcm}(x\cdot a_1, x\cdot a_2, \ldots, x\cdot a_k) = x\cdot \text{lcm}(a_1, a_2, \ldots, a_k)
That is, multiplying all the numbers of a sequence by a constant multiplies the gcd/lcm of the sequence by the same constant.
Proofs of these can be found here.
Further, note that if the gcd and lcm are multiplied by the same constant, their ratio remains the same!
In particular, notice that A^{(k)} is obtained from A^{(k-1)} via multiplication by a constant.
This means that \displaystyle \frac{L_k}{G_k} = \frac{L_0}{G_0} for all k \geq 0, since each array is obtained in succession via multiplication with a constant.
However, \displaystyle\frac{L_k}{G_k} is also the constant we multiply A^{(k)} with to get A^{(k+1)}.
So, we simply have
which can both be found in \mathcal{O}(\log k) time using binary exponentiation, since we already know G_0 and L_0.
TIME COMPLEXITY
\mathcal{O}(10^7 \log\log {10^7} + N\log 10^7 + Q\log {MOD}) per testcase.
CODE:
Author's code (C++)
#include <bits/stdc++.h>
#define el '\n'
typedef long long ll;
typedef long double ld;
#define Beevo ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
const int N = 1e7 + 5, M = 1e9 + 7;
int spf[N], maxFreq[N];
int mul(int a, int b) {
return 1LL * a * b % M;
}
int modPow(int b, int p) {
if (!p)
return 1;
int x = modPow(b, p / 2);
return p % 2 == 0 ? mul(x, x) : mul(b, mul(x, x));
}
int modInvFer(int n) {
return modPow(n, M - 2);
}
void sieve() {
for (int i = 1; i < N; i++)
spf[i] = i;
for (int i = 2; i * i < N; i++) {
if (spf[i] == i) {
for (int j = i * 2; j < N; j += i)
spf[j] = min(spf[j], i);
}
}
}
void factorize(int n) {
int pf, freq;
while (n > 1) {
pf = spf[n], freq = 0;
while (n % pf == 0)
freq++, n /= pf;
maxFreq[pf] = max(maxFreq[pf], freq);
}
}
void testCase() {
sieve();
int n;
cin >> n;
int g = 0;
for (int i = 0, a; i < n; i++)
cin >> a, g = __gcd(g, a), factorize(a);
int l = 1;
for (int i = 1; i < N; i++)
l = mul(l, modPow(i, maxFreq[i]));
int q;
cin >> q;
int k, p, d = mul(l, modInvFer(g));
while (q--) {
cin >> k;
p = modPow(d, k);
cout << mul(g, p) << ' ' << mul(l, p) << el;
}
}
signed main() {
Beevo
int t = 1;
// cin >> t;
while (t--)
testCase();
}
Editorialist's code (Python)
from math import gcd
lim = 10**7 + 10
mod = 10**9 + 7
primefac = [1]*lim
for i in range(2, lim):
if primefac[i] == 1:
for j in range(i, lim, i): primefac[j] = i
n = int(input())
a = list(map(int, input().split()))
g, l = a[0], 1
mxpow = [0]*lim
for x in a:
g = gcd(x, g)
while x > 1:
p = primefac[x]
ct = 0
while x%p == 0:
x //= p
ct += 1
mxpow[p] = max(mxpow[p], ct)
for x in range(2, lim):
if primefac[x] != x: continue
l *= pow(x, mxpow[x], mod)
l %= mod
for _ in range(int(input())):
k = int(input())
mul = pow(l, k, mod) * pow(g, k*(mod-2), mod) % mod
print(g * mul % mod, l * mul % mod)