@amanchourasiya You are getting correct answer in subtask 2?
No RE. But I am geting WA in subtask 1 which is bothering me as to why?
Should be (a*b) // gcd(a,b).
In Python 3 integer division is ‘//’. The result of a single ‘/’ is a double.
1 Like
According to my solution,If there are multiple solution then answer will always 1.
Is this approach correct?
Hi Can anyone help me with the very different problem I am able to get the success in the original constrain but getting the wrong answer in subtask#1 if anyone can tell me why. @ezio_26
import math as mt
MAXN = 100001
spf = [0 for i in range(MAXN)]
def sieve():
spf[1] = 1
for i in range(2, MAXN):
spf[i] = i
for i in range(4, MAXN, 2):
spf[i] = 2
for i in range(3, mt.ceil(mt.sqrt(MAXN))):
if (spf[i] == i):
for j in range(i * i, MAXN, i):
if (spf[j] == j):
spf[j] = i
def getFactorization(x):
# ret = list()
d = dict()
while (x != 1):
d[spf[x]] = d.get(spf[x],0)+1
# ret.append(spf[x])
x = x // spf[x]
return d
sieve()
factor = {}
for x in range(1,10001):
factor[x]=getFactorization(x)
# print(factor)
# l = [2,4,5,10,45]
for i in range(int(input())):
n , m = map(int,input().split())
l = list(map(int, input().split()))
curlcm = 1
lcm = {}
# l = [2,5,6,3]
for i in l:
for j in factor[i]:
try:
if lcm[j] >= factor[i][j]:
continue
else:
t = lcm[j]
lcm[j] = factor[i][j]
curlcm *= j*(factor[i][j]-t)
except KeyError:
lcm[j] = factor[i][j]
curlcm *= j * factor[i][j]
# print(curlcm)
maxlcm = curlcm
index = 1
for i in range(1,m+1):
dc = curlcm
for j in factor[i]:
try:
if lcm[j] >= factor[i][j]:
continue
else:
t = lcm[j]
lcm[j] = factor[i][j]
dc *= j ** (factor[i][j] - t)
except KeyError:
f = True
dc *= j ** factor[i][j]
if maxlcm < dc:
maxlcm = dc
index = i
print(index)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});
}`
This portion of the sieve used in the setter’s solution itself has a time complexity of N*π(N) where π(N) is the number of prime numbers less than or equal to N.
This makes the time complexity of the solution much higher than what is claimed.
N*\pi \left ( N \right ) \sim \frac{ N^{2}}{logN}
1 Like
1
4 10000
9985 9998 9996 9885
test case which helped me get ac incase useful to any1.
ans = 9997
I am following the same solution as the Editorialist but still getting TLE in subtask 2. Can someone tell me how I can optimise it furthur?
Link to my code : LSJU9H - Online C++0x Compiler & Debugging Tool - Ideone.com
Hi, the code is using maps to store the power of each factor of each number in the array,
then it stores the product of all the powers of the factors which are greater than the maximum power of that factor in the array;
example:
array : 81 4
map stores:
2 2
3 4
but this is not working, can someone help debug the code?
#include<iostream>
#include<map>
using namespace std;
int main()
{
int test;
cin>>test;
while(test--)
{
int n,m;
cin>>n>>m;
int temp;
map<int,int> mp;
for(int i=0;i<n;i++)
{
cin>>temp;
map<int,int> mp3;
for(int j=2;j*j<=temp;j++)
{
while(temp%j==0)
{
temp/=j;
mp3[j]++;
}
if(mp[j]<mp3[j]) mp[j]=mp3[j];
}
}
int ans=0;
int pos=1;
for(int i=1;i<=m;i++)
{
int temp=1;
map<int,int> mp3;
for(int j=2;j*j<=i;j++)
{
while(i%j==0)
{
i/=j;
mp3[j]++;
}
cout<<j<<" "<<mp3[j]<<endl;
if(mp[j]<mp3[j]) temp*=(mp3[j]-mp[j]);
}
if(ans<temp) {ans=temp; pos=i;}
}
cout<<pos<<endl;
}
}
@taran_1407 won’t the complexity of your code be O( (N + M) * log(M)) ? because while processing N values and M values, you are using the exact same logic.
Can anyone help me with my code → It gave WA on second task of subtask2 , rest all are passed. there might be very small edge case mistake , i am not abe to figure out.
My Code
I used smallest prime factor of a number for prime factorization.
@tushar_18030 I have highlighted the correction in the code here.
The problem was in the formulae which counted the change contributed by a number.
Hope this helped 
1 Like
Thank u so much 
@anon70769165 calculating the LCM from the prime factorization will overflow even the range of long long int (also mentioned in the editorial). Whole motive of calculating the prime factorization of LCM was to use it to calculate the change contributed by i (1 <= i <= M) to the LCM
see this video to know how to calculate the change contributed by i
@anon14510829 I have highlighted the change as to why the powers of prime factorizations were incorrect in this code.
But still it needed to be further optimized to pass the test case as creating a new map for each iteration where a single variable can be used is really redundant and slow.
@jerry_storm here, the optimized version of your code.
Actually again and initializing temp[] for each n values was taking too much time.