@taran_1407 Thanks I got it now. I was getting confused when X>l but now I am clear.
I am trying to implement the solution but getting wrong answer.Can you help me where I am getting wrong.Here is the link
https://www.codechef.com/viewsolution/30909776
I tried to implement the same during the contest. But now I know I was wrong approaching like that due to Overflow issue.Even long long will not be able to contain that large value.
you can’t store lcm of these no in even after using long long
2 Likes
Python 3 solution
sol : CodeChef: Practical coding for everyone
I have used the approach mentioned in editorial still it give TLE on last Subtask. Can someone help me? I have the same problem
can anybody help me to understand why i am getting wrong answer??
here is my code:
////////////////////////////////////////////////////////////////////////////////////////
#include <bits/stdc++.h>
#include
#include
#include
#include
#include<string.h>
using namespace std;
int b[10001]={0};
void primeFactors(long long int n)
{
// Print the number of 2s that divide n
while (n % 2 == 0)
{
b[2]+=1;
//cout << 2 << " ";
n = n/2;
}
// n must be odd at this point. So we can skip
// one element (Note i = i +2)
for (int i = 3; i <= sqrt(n); i = i + 2)
{
while (n % i == 0)
{
b[i]+=1;
//cout << i << " ";
n = n/i;
}
}
if (n > 2)
b[n]+=1;
//cout << n << " ";
}
int main()
{
int t;
cin>>t;
for(int i=0;i<t;i++)
{
int n,m;
cin>>n>>m;
int a[n],c[m+1]={0};
unsigned long long int d[m+1]={0};
for(int i=0;i<n;i++)
cin>>a[i];
for(int i=0;i<n;i++)
primeFactors(a[i]);
for(int i=1;i<=m;i++)
{ c[i]=b[i]; b[i]=0;}
// for(int i=1;i<=m;i++)
// cout<<b[i]<<" ";
unsigned long long int x=1;
for(int i=1;i<=m;i++)
{
primeFactors(i);
x=1;
for(int j=1;j<=m;j++)
{
if(b[j]!=0)
{
b[j]=(c[j]>b[j])?0:(b[j]-c[j]);
x=pow(j,b[j])*x;
b[j]=0;
}
}
d[i]=x;
}
unsigned long long int max=0;
int index=1;
for(int i=1;i<=m;i++)
{
if(max<d[i])
{ max=d[i];index=i;}
}
cout<<index<<endl;
}
return 0;
}
But without optimization also running a loop if it completes within time should not give WA as verdict. However it is doing so in my case.
But why the verdict in subtask coming out to be wrong?
But what if we use python 3 instead of cpp. I dont think overflow is then a issue. But the answer is going wrong then in subtask 1.
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;
}
}