# MINIMUMOP - Editorial

Author: satyam_343
Tester: yash_daga
Editorialist: iceknight1093

2170

# PREREQUISITES:

Fast prime factorization, Sieve of Eratosthenes

# PROBLEM:

You have an array A of length N, such that 2\leq A_i \leq M.
In one move, you can select an integer X and set A_i \gets \gcd(A_i, X) for every i.

Find the minimum number of moves needed to make all the array elements equal.

# EXPLANATION:

If all the A_i are already equal, the answer is 0. We need to solve for the case when they aren’t.

Notice that choosing X = 2 sets every A_i to either 1 or 2.
Choosing X = 3 after this sets everything to 1, since \gcd(1, 3) = \gcd(2, 3) = 1.

So, it’s always possible to make everything equal within two moves. All we need to check is whether everything can be made equal in 1.

Suppose we are able to do this, and make all the array elements equal to Y in the end.
There are two possibilities here: either Y = 1, or Y \gt 1.

Y = 1

We want to choose 2 \leq X \leq M such that \gcd(A_i, X) = 1 for every A_i.

In particular, this means that X cannot share a prime factor with any of the A_i; if it did, then the corresponding gcd wouldn’t be 1.

So, suppose we have a list of all the prime factors of all the A_i, say L.
We need to check if there’s an X between 2 and M that doesn’t have a prime factor in L.
Notice that it’s enough to restrict ourselves to the case when X is prime.

So, we simply need to check whether there’s any prime in the range [2, M] that isn’t in L.
If the primes upto M are precomputed (using a sieve), this is easy to do (given that you have L in hand, of course).

Finally, we also need to discuss how to compute the list L quickly, i.e, how to prime-factorize all the A_i quickly.
The constraints are low enough that directly factorizing each number in \mathcal{O}(\sqrt {A_i}) is probably fast enough, but there’s a faster way using the fact that A_i \leq 5\cdot 10^5.

In the initial sieve we do to find prime numbers, also store one prime divisor of each number, let’s call it \text{prm}[x] for x.
Then, to prime factorize A_i:

• \text{prm}[A_i] is one prime factor.
• The next prime factor can be found by dividing \text{prm}[A_i] out of A_i and again looking at the \text{prm} array, i.e, looking at \text{prm}\left[\frac{A_i}{\text{prm}[A_i]}\right].
• Repeat this while A_i \gt 1.

Each division (at least) halves A_i, so this will take \log{A_i} steps.
This allows us to obtain all the prime factors of the A_i in \mathcal{O}(N\log M) time.

Putting everything together, the solution for this case looks as follows:

• Quickly prime factorize all the A_i, either using the method outlined above or otherwise.
Let L be the list of all prime factors of all the A_i.
• Then, for each prime p from 2 to M:
• If p is present in L, continue on. This can be checked quickly using, say, binary search.
• If p is not present in L, then performing one operation with p is valid, and you can break out immediately.

Note that as long as you break out immediately, this is fast enough even though there’s no constraint on the sum of M across all tests.
This is because the list L contains at most N\log M elements. So,

• If a valid prime is found, it’ll certainly be within N\log M + 1 steps at most, each taking one binary search. This is not a problem.
• If no valid prime is found, then N\log M must exceed the number of primes from 1 to M, which is approximately \frac{M}{\log M} by the prime number theorem.
This roughly gives us a lower bound on N, something like N \geq \frac{M}{\log ^2 M}.
Since the sum of N across all cases is bounded, we’re fine.
Y > 1

Suppose we’re able to choose an X such that \gcd(A_i, X) = Y for every i, and Y \gt 1.

Notice that Y must be a factor of both X and A_i — in fact, Y must be a factor of every A_i.
This means Y must be factor of \gcd(A_1, A_2, \ldots, A_N), by definition of \gcd.

In particular, if \gcd(A_1, \ldots, A_N) = 1, then such a Y cannot exist.
On the other hand, if \gcd(A_1, \ldots, A_N) \gt 1, then simply choosing X = \gcd(A_1, \ldots, A_N) will also give us Y = \gcd(A_1, \ldots, A_N) \gt 1, and we’ll be done!

Check both cases above to see if using one move is possible.
If both cases fail, then the answer is 2, using X = 2 and X = 3 as discussed above.

As an aside, the technique of prime-factorizing numbers using a sieve is fairly common, and even appeared in GCD_QUERIES from last week.

# TIME COMPLEXITY

\mathcal{O}(N\log^2 M) per test case with a sieve upto 10^6 as precomputation.

# CODE:

Setter's code (C++)
#pragma GCC optimization("O3")
#pragma GCC optimization("Ofast,unroll-loops")

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
#define ll long long
const ll INF_MUL=1e13;
#define pb push_back
#define mp make_pair
#define nline "\n"
#define f first
#define s second
#define pll pair<ll,ll>
#define all(x) x.begin(),x.end()
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vvvl vector<vector<vector<ll>>>
#ifndef ONLINE_JUDGE
#define debug(x) cerr<<#x<<" "; _print(x); cerr<<nline;
#else
#define debug(x);
#endif
void _print(ll x){cerr<<x;}
void _print(int x){cerr<<x;}
void _print(char x){cerr<<x;}
void _print(string x){cerr<<x;}
template<class T,class V> void _print(pair<T,V> p) {cerr<<"{"; _print(p.first);cerr<<","; _print(p.second);cerr<<"}";}
template<class T>void _print(vector<T> v) {cerr<<" [ "; for (T i:v){_print(i);cerr<<" ";}cerr<<"]";}
template<class T>void _print(set<T> v) {cerr<<" [ "; for (T i:v){_print(i); cerr<<" ";}cerr<<"]";}
template<class T>void _print(multiset<T> v) {cerr<< " [ "; for (T i:v){_print(i);cerr<<" ";}cerr<<"]";}
template<class T,class V>void _print(map<T, V> v) {cerr<<" [ "; for(auto i:v) {_print(i);cerr<<" ";} cerr<<"]";}
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset;
typedef tree<pair<ll,ll>, null_type, less<pair<ll,ll>>, rb_tree_tag, tree_order_statistics_node_update> ordered_pset;
//--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
const ll MOD=1e9+7;
const ll MAX=1000500;
vector<ll> freq(MAX,0);
vector<ll> prime(MAX,1);
vector<vector<ll>> track(MAX);
void solve(){
ll n,m; cin>>n>>m;
vector<ll> a(n);
for(auto &it:a){
cin>>it;
}
sort(all(a));
if(a==a[n-1]){
cout<<0<<nline;
return;
}
for(auto it:a){
for(auto i:track[it]){
freq[i]++;
}
}
auto init=[&](){
for(auto it:a){
for(auto i:track[it]){
freq[i]=0;
}
}
};
for(ll i=2;i<=m;i++){
if(!prime[i]){
continue;
}
if(freq[i]==0 or freq[i]==n){
init();
cout<<1<<nline<<i<<nline;
return;
}
}
init();
cout<<2<<nline<<2<<" "<<3<<nline;
return;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
freopen("error.txt", "w", stderr);
#endif
ll test_cases=1;
cin>>test_cases;
prime=0;
for(ll i=2;i<MAX;i++){
if(!prime[i]){
continue;
}
for(ll j=i+i;j<MAX;j+=i){
prime[j]=0;
track[j].push_back(i);
}
track[i].push_back(i);
}
while(test_cases--){
solve();
}
cout<<fixed<<setprecision(10);
cerr<<"Time:"<<1000*((double)clock())/(double)CLOCKS_PER_SEC<<"ms\n";
}

Tester's code (C++)
//clear adj and visited vector declared globally after each test case
//check for long long overflow
//Mod wale question mein last mein if dalo ie. Ans<0 then ans+=mod;
//Incase of close mle change language to c++17 or c++14
//Check ans for n=1
#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
// #define int long long
#define IOS std::ios::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL);cout.precision(dbl::max_digits10);
#define pb push_back
#define mod 1000000007ll //998244353ll
#define lld long double
#define mii map<int, int>
#define pii pair<int, int>
#define ll long long
#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()
#define rep(i,x,y) for(int i=x; i<y; i++)
#define fill(a,b) memset(a, b, sizeof(a))
#define vi vector<int>
#define setbits(x) __builtin_popcountll(x)
#define print2d(dp,n,m) for(int i=0;i<=n;i++){for(int j=0;j<=m;j++)cout<<dp[i][j]<<" ";cout<<"\n";}
typedef std::numeric_limits< double > dbl;
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
//member functions :
//1. order_of_key(k) : number of elements strictly lesser than k
//2. find_by_order(k) : k-th element in the set
const long long N=1000005, INF=2000000000000000000;
const int inf=2e9 + 5;
lld pi=3.1415926535897932;
int lcm(int a, int b)
{
int g=__gcd(a, b);
return a/g*b;
}
int power(int a, int b, int p)
{
if(a==0)
return 0;
int res=1;
a%=p;
while(b>0)
{
if(b&1)
res=(1ll*res*a)%p;
b>>=1;
a=(1ll*a*a)%p;
}
return res;
}

int getRand(int l, int r)
{
uniform_int_distribution<int> uid(l, r);
return uid(rng);
}
vi pfact[N];
int co[N];
int32_t main()
{
IOS;
for(int i=2;i<N;i++)
{
if(pfact[i].size()==0)
{
for(int j=i;j<N;j+=i)
pfact[j].pb(i);
}
}
int t;
cin>>t;
while(t--)
{
int n, m;
cin>>n>>m;
int a[n];
rep(i,0,n)
cin>>a[i];
sort(a, a+n);
if(a==a[n-1])
{
cout<<0<<"\n";
continue;
}
rep(i,0,n)
{
for(auto p:pfact[a[i]])
co[p]++;
}
int f=0;
rep(i,2,m+1)
{
if(pfact[i]!=i)
continue;
if(co[i]==0 || co[i]==n)
{
f=i;
break;
}
}
rep(i,0,n)
{
for(auto p:pfact[a[i]])
co[p]=0;
}
if(f)
cout<<1<<"\n"<<f<<'\n';
else
cout<<2<<"\n"<<m<<" "<<m-1<<"\n";
}
}

Editorialist's code (Python)
mx = 10**6 + 314
prm = *mx
for i in range(2, mx):
if prm[i] > 0: continue
for j in range(i, mx, i): prm[j] = i

from math import gcd
for _ in range(int(input())):
n, m = map(int, input().split())
a = list(map(int, input().split()))
if min(a) == max(a):
print(0)
continue

ans = -1
g = a
primes = set()
for x in a:
g = gcd(x, g)
while x > 1:
x //= prm[x]
if g > 1: ans = g

for x in range(1, m+1):
if prm[x] < x: continue
if x not in primes:
ans = x
break

if ans == -1: print(2, '\n', 2, ' ', 3, sep = '')
else: print(1, '\n', ans, sep = '')


Number of prime numbers between 2 and 1e6 is around 79,000 so iterating through all the primes numbers should give TLE rright ? because number of test cases are 1e5.

Please read the editorial fully, specifically the end of the Y = 1 section.
I’ve outlined why it doesn’t TLE if you break out quickly.

In case Y = 1, checking if there’s any prime in the range [2, M] that isn’t in L can be done by binary searching the smallest prime over the primes list (let’s call it P) that isn’t in L as follows:

1. Sort the list L and remove any duplicates in it (P is assumed to be sorted as well).
2. Now, we know that P and L share some prefix, so we’re going to binary search the first index such that the prefixes of P and L are not equal, if P[mid] == L[mid] then the prefix [0, mid] is the same and we can safely eliminate the range [0, mid] and look into the range [mid + 1, MAX\_INDEX], otherwise the smallest prime would be in the range [0, mid].
3. This will get us the smallest prime in P that isn’t in L, and then we only have to make sure that this prime is in the range [2, M].

You can refer to this submission for more details.

1 Like

What should be the answer to the following test case:
1
4 2
2 3 4 5

The tester’s code returns ans the following:
2
2 1
But as per the question we cannot have X = 1.
In general , if M = 2, then in arr there will be some 2’s and some 1’s. How do we even make them equal ? Also I didn’t find any mention in the problem statement that this won’t be the test case?

This is not a valid test case, because the elements of the array are also restricted by M, it’s stated as below, and in the constraints section as well:

You are also given an array A of size N, such that 2 \leq A_i \leq M.

The time complexity of my code is M logM , I don’t know why last two test cases are tle. I’ve used sieve prime factorization.
https://www.codechef.com/viewsolution/94985376

You’re sieving once for each test case, that won’t work because, as the constraints section says,

Note that sum of M over all test case isn't bounded.


You need to sieve once upto 10^6 and then reuse that sieve across all testcases.

1 Like