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. 