MXMLCM - Editorial

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2

Setter: Hasin Rayhan Dewan Dhruboo
Tester: Teja Vardhan Reddy
Editorialist: Taranpreet Singh

DIFFICULTY:

Easy

PREREQUISITES:

Number-theory, Sieve of Eratosthenes

PROBLEM:

Given N numbers within the range [1, M], Let’s denote L as the LCM of given numbers. You are allowed to choose one number in the range [1, M] such that after adding this number to the array, the LCM is maximized. If multiple such numbers exist, determine the smallest such number.

QUICK EXPLANATION

  • We only care about the prime factorization of L. To obtain prime factorization of L, for each prime, we just find the largest power of that prime, which divides any number in the array.
  • The final LCM would be LCM(L, X) if X is added, which is same as L*X/GCD(L, X)
  • We can check all values in range [1, M] and choose the smallest X with the maximum value of X/GCD(L, X).

EXPLANATION

Let’s first compute the existing LCM of the given array. But we cannot store it in even long long, but we can see that all prime factors must be up to M, so we can store prime factorization of LCM in array F, where F_p denote the power of prime p in factorization L.

It’s easy to compute LCM of the given array since we can factorize each value and find the maximum of powers of each prime which divides at least one element from the array.

Now, Suppose we add value X into the array. The resulting LCM would be LCM(L, X) which can also be written as L*X/GCD(L, X). Now, L remains the same, so we need to choose the smallest X such that X/GCD(L, X) is maximum possible.

Open this only after trying to solve

For this, we can try each value from 1 to M, we can find GCD(L, X) by taking the product of p^{min(F_p, X_p)} for each prime, where X_p denote the largest power of prime p dividing X. We can compare and find the required answer.

If any doubt, refer to the solutions attached below.

TIME COMPLEXITY

The time complexity is O(N+M*log(M)) per test case.

SOLUTIONS:

Setter's Solution
#include<bits/stdc++.h>
using namespace std;
const int maxn = 10009;
int n, m;
int t, cs = 1;
int ara[maxn];
vector < pair < int , int > > divs[maxn + 7];

int perPrime[maxn + 7];

void sieve(int n)
{
	for(int i = 2; i <= n; i++){
	    if(divs[i].size()) continue;
	    for(int j = i; j <= n; j += i) divs[j].push_back({i, 0});
	}

	for(int i = 2; i <= n; i++){
	    for(int j = 0; j < divs[i].size(); j++){
	        int cur = divs[i][j].first;
	        int cnt = 0, val = i;
	        while(val % cur == 0) val = val / cur, cnt++;
	        divs[i][j].second = cnt;
	    }
	}
}

int main()
{
	cin >> t;
	sieve(maxn);

	while(t--){
	    scanf("%d %d", &n, &m);
	    memset(perPrime, 0, sizeof(perPrime));
	    for(int i = 1; i <= n; i++){
	        scanf("%d", &ara[i]);
	        for(auto dv : divs[ara[i]]) perPrime[dv.first] = max(perPrime[dv.first], dv.second);
	    }

	    int mxmLCM = 0, mxmAns = 0;

	    for(int i = 1; i <= m; i++){

	        int barbe = 1;
	        for(auto dv : divs[i]){
	            int dif = max(0, dv.second - perPrime[dv.first]);
	            for(int i = 1; i <= dif; i++) barbe = barbe * dv.first;
	        }
	        if(barbe > mxmLCM){
	            mxmLCM = barbe;
	            mxmAns = i;
	        }
	    }
	    printf("%d\n", mxmAns);
	}

	return 0;
}
Tester's Solution
//teja349
#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip>
//setbase - cout << setbase (16); cout << 100 << endl; Prints 64
//setfill -   cout << setfill ('x') << setw (5); cout << 77 << endl; prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
//cout.precision(x)  cout<<fixed<<val;  // prints x digits after decimal in val
 
using namespace std; 
#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod (1000*1000*1000+7)
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >
#define flush fflush(stdout) 
#define primeDEN 727999983
 

int pr[123456],a[123456],b[123456];
int getans(int val){
	int previ=1,sofar=0;
	int i,ans=1;
	while(1){
		if(previ==pr[val])
			sofar++;
		else{
			f(i,b[previ],sofar){
				ans*=previ;
			}
			previ=pr[val];
			sofar=1;
		}
		if(val==1)
			return ans;
		val/=pr[val];
	}
}
int factorise(int val){
	int previ=1,sofar=0;
	int i,ans=1;
	while(1){
		if(previ==pr[val])
			sofar++;
		else{
			b[previ]=max(b[previ],sofar);
			previ=pr[val];
			sofar=1;
		}
		if(val==1)
			return ans;
		val/=pr[val];
	}
} 
int main(){
	std::ios::sync_with_stdio(false); cin.tie(NULL);
	int i,j;
	pr[1]=0;
	for(i=2;i<123456;i++){
		if(pr[i])
			continue;
		pr[i]=i;
		for(j=2*i;j<123456;j+=i){
			if(pr[j]==0)
				pr[j]=i;
		}
	}
	int t;
	cin>>t;
	while(t--){
		int n,m;
		cin>>n>>m;
		rep(i,m+2){
			b[i]=0;
		}	
		rep(i,n){
			cin>>a[i];
			if(a[i]==1)
				continue;
			factorise(a[i]);
		}
		int ans=1,maxi=1,val;
		f(i,2,m+1){
			val=getans(i);
			if(maxi<val){
				ans=i;
				maxi=val;
			}
		}
		cout<<ans<<endl;
	}
}
Editorialist's Solution
import java.util.*;
import java.io.*;
import java.text.*;
class MXMLCM{
	//SOLUTION BEGIN
	int mx = (int)1e4;
	int[] spf;
	void pre() throws Exception{
	    spf = new int[1+mx];//spf[i] -> smallest prime factor of i
	    spf[0] = spf[1] = 1;
	    for(int i = 2; i<= mx; i++)
	        if(spf[i] == 0)
	            for(int j = i; j<= mx; j+= i)
	                if(spf[j] == 0)
	                    spf[j] = i;
	}
	void solve(int TC) throws Exception{
	    int n = ni(), m = ni();
	    int[] f = new int[1+m];//Storing prime factorization of lcm
	    for(int i = 0; i< n; i++){
	        int x = ni();
	        while(x > 1){
	            int p = spf[x];
	            int c = 0;
	            while(x%p == 0){x/=p;c++;}//p^c divides x, but p^(c+1) doesn't
	            f[p] = Math.max(f[p], c);
	        }
	    }
	    int ans = 1, factor = 1;
	    for(int i = 2; i<= m; i++){
	        int gain = 1;
	        int x = i;
	        while(x > 1){
	            int p = spf[x];
	            int c = 0;
	            while(x%p == 0){x/=p;c++;}
	            c -= f[p];//Removed common power
	            while(c-->0)gain *= p;//Computed remaining
	        }
	        if(gain > factor){
	            ans = i;
	            factor = gain;
	        }
	    }
	    pn(ans);
	}
	//SOLUTION END
	void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
	DecimalFormat df = new DecimalFormat("0.00000000000");
	static boolean multipleTC = true;
	FastReader in;PrintWriter out;
	void run() throws Exception{
	    in = new FastReader();
	    out = new PrintWriter(System.out);
	    //Solution Credits: Taranpreet Singh
	    int T = (multipleTC)?ni():1;
	    pre();for(int t = 1; t<= T; t++)solve(t);
	    out.flush();
	    out.close();
	}
	public static void main(String[] args) throws Exception{
	    new MXMLCM().run();
	}
	int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
	void p(Object o){out.print(o);}
	void pn(Object o){out.println(o);}
	void pni(Object o){out.println(o);out.flush();}
	String n()throws Exception{return in.next();}
	String nln()throws Exception{return in.nextLine();}
	int ni()throws Exception{return Integer.parseInt(in.next());}
	long nl()throws Exception{return Long.parseLong(in.next());}
	double nd()throws Exception{return Double.parseDouble(in.next());}

	class FastReader{
	    BufferedReader br;
	    StringTokenizer st;
	    public FastReader(){
	        br = new BufferedReader(new InputStreamReader(System.in));
	    }

	    public FastReader(String s) throws Exception{
	        br = new BufferedReader(new FileReader(s));
	    }

	    String next() throws Exception{
	        while (st == null || !st.hasMoreElements()){
	            try{
	                st = new StringTokenizer(br.readLine());
	            }catch (IOException  e){
	                throw new Exception(e.toString());
	            }
	        }
	        return st.nextToken();
	    }

	    String nextLine() throws Exception{
	        String str = "";
	        try{   
	            str = br.readLine();
	        }catch (IOException e){
	            throw new Exception(e.toString());
	        }  
	        return str;
	    }
	}
}

Feel free to share your approach. Suggestions are welcomed as always. :slight_smile:

5 Likes

The test cases are too tight. Prime factorization without seive throws TLE.

1 Like

I’m trying different approach and I know I’m wrong but where?
What I’m trying to do is finding the maximum prime number within range [m]. and if this prime number is not in the sequence than printing this as the answer. The idea behind this is that LCM is nothing but the multiplication of prime number.
So if I able to add one new prime number into it I’ll get the maximum LCM.
Please tell me where I’m wrong in this approach?

if the given array is {1,3,5} and M is 5 the you’ll add 4 to array for maximum LCM which is not a prime number

.You can pre - process the prime factors from 1 to 10^4 before solving for test cases.After you have done it ,you can loop from 1 to M for every test case in upper-bound of M*log(M) time complexity which will be sufficient for out 1 s time limit .
My Code : https://ide.geeksforgeeks.org/6eiS7rSiPC

I’m iterating through the prime numbers and 4 is not a prime number so my algorithm will output 2 for this test case. Which is correct answer

LCM of {1,3,4,5} is 60 while for {1,2,3,5} is 30 therefore 4 is the answer.
We want to maximize the LCM and only take the smaller value when we have multiple solutions

thank you. Now I get it. Actually I totally forget about the co-prime and strictly checking for primes.

I was doing the same mistake. Consider this case, your m = 36, and array is {1,3,6} now what your program will do is print 29 but 35 is the right answer. You need to consider your array as well and check whether its the number that you are adding has its prime factors in array or not. If not then that number will be your answer.

I am using the naive approach.
Find the LCM of the array and then a loop 1 to M to get Max LCM.
Getting wrong answer.

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

int gcd(int a, int b)
{
if (a == 0)
return b;
return gcd(b % a, a);
}
int lcm(int a, int b)
{
return (a * b) / gcd(a, b);
}

int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);

cin >> t;
while (t--)
{
    int n, m, l = 1;
    cin >> n >> m;
    int arr[n];
    for (int i = 0; i < n; ++i)
        cin >> arr[i];
    for (int i = 0; i < n; ++i)
        l = lcm(l, arr[i]);

    
    int lm = l;
    int ma = 1;

    for (int i = 1; i <= m; ++i)
        if (lm < lcm(l, i))
        {
            lm = lcm(l, i);
            ma = i;
        }
    cout << ma << endl;
}

return 0;

}

There is a simpler and easy method to achieve the same result.

You can check what will contribute the max to the LCM. The Code is Quite Simple to understand.`

#include<bits/stdc++.h>

#define ll long long
#define mi map<int,int>
#define endl ‘\n’
#define loop(i,a,b) for(int (i)=(a);(i)<(b);(i)++)

using namespace std;

void sol(){
int n , m ; cin >> n >> m ;
mi F;loop(i,0,n){
ll x ; cin >> x;
for(ll j=2;jj<=x;++j){
if(x%j==0){
int c =0 ;while(x%j==0) x/=j,c++;
F[j]=max(F[j],c);
}
if(x==1) break;
}
if(x!=1) F[x]=max(F[x],1);
}
int v=1,mxv=1;
loop(i,2,m+1){
ll x = i,lmx=1;
for(int j=2;j
j<=x;++j){
if(x%j==0){
int c =0 ;while(x%j==0) x/=j,c++;
if(c>F[j]) lmx *= (int)pow(j,c-F[j]);
}
}
if(x!=1 && F[x]==0) lmx *= x;
if(lmx>mxv) mxv=lmx,v=i;
}
cout << v << endl;
}

int main(){
int t; cin >> t ; while(t–) sol();
return 0;
}`

What is wrong in this python code somebody plz tell me??

> def gcd(a, b):
>     if(b == 0):
>         return a
>     return gcd(b, a%b)
> 
> def findlcm(l, n):
>     ansx = l[0]
>     for i in range(n):
>         ansx = lcm(ansx, l[i])
> 
> def lcm(a, b):
>     return (a*b)/gcd(a,b)
> 
> def solve():
>     n, m = [int(i) for i in input().split()]
>     l = [int(i) for i in input().split()]
>     init_lcm = findlcm(l, n)
>     ans = 1
>     track = init_lcm
>     for i in range(1, m + 1):
>         m = lcm(init_lcm, i)
>         if(m > track):
>             track = m
>             ans = i
>     print(ans)
> 
> t =int(input())
> while(t > 0){
>     t -= 1
>     solve()
> }

So have you got your answer. I have a similar approach but in python getting the same wrong answer as verdict.

why not find lcm of array, then loop through 1 to m finding the lcm for each. default value is 1
But this approach gives WA

An optimization - start from X = M down and stop when X become less than the current maximum of X / GCD(L, X).

1 Like

This gets subtask 1, but TLE on subtask 2 when lcm of the entire array is huge.

1 Like

Are you sure that it is easy to understand an unformatted code?

1 Like

@taran_1407 Just wanted to clear one thing wouldn’t the gain term in your solution overflow?Can you explain it a bit.

https://www.codechef.com/viewsolution/30907755 why it is showing tle? @pritishn

We have gain = X/GCD(L, X) where L is LCM. We also know that GCD(A, B) \leq min(A, B), so its easy to see that 1 \leq gain \leq X

1 Like