18
Let’s say N=18, so 18 if you choose K=2, M=9 and it has 3 factors (1,3,9) while if you choose K=3, M= 6 and it has 4 factors (1,2,3,6) so your answer will be 3 here.
5 Likes
Square number is just a pain. example 25*2 = 50 or (prime_number^2)*2
example 98,50,18 and so on
9036011=3001*3011, answer should be 3001 but you will print 9036011 ig.
1 Like
Some one please let me know why I’m getting TLE. Thanks
#include<bits/stdc++.h>
#define int long long
#define endl ‘\n’
#define FAST_IO ios_base::sync_with_stdio(false);cin.tie(NULL)
using namespace std;
int32_t main()
{
FAST_IO;
int t;cin>>t;
int limit = sqrt(1e9);
vector<bool> mark(limit, true);
for (int p=2; p*p<limit; p++)
{
// If p is not changed, then it is a prime
if (mark[p] == true)
{
// Update all multiples of p
for (int i=p*p; i<limit; i+=p)
mark[i] = false;
}
}
// Print all prime numbers and store them in prime
vector<int> prime;
for (int p=2; p<limit; p++)
{
if (mark[p] == true)
{
prime.push_back(p);
}
}
while(t--){
int n;cin>>n;
int ans = n;
map<int,int> fr;
fr[n]=1;
int r = 1;
int sz = prime.size();
for(int i=sz-1;i>=0;i--)
{
if(r>n)
break;
int p = prime[i];
int temp = 0;
int val = n;
while(val>=p && ((val%p) == 0))
{
temp++;
val/=p;
r*=p;
}
fr[p]=temp;
if(temp>fr[ans])
ans=p;
else if(temp==fr[ans] && p<ans)
ans=p;
}
cout<<ans<<endl;
}
}
/*
3*2
*/
Clearly the answer will be a prime divisor of n. Factorise n and compute the number of it’s divisors and it’s prime decomposition in \mathcal O(\sqrt{n}). Now loop over each prime divisor p, which let’s say appears k times. If the number of divisors of n is \tau(n), then we can note that \tau(n/p) = \dfrac{k\tau(n)}{k+1}. We can maximise this over all primes and then take the smallest value of p achieveing the above.
You are trying to store all the prime numbers till 10^9, dude generally in 1 sec we can perform operations of 10^7 order but here in the sieve itself operations will be more than 10^10. Hence it will result in TLE.
1 Like
Someone please tell me why f[0].first is the answer? What I’m understanding from the editorial is:
-
Find prime factorization of N.
-
smallest factor which have maximum exponent will be considered as K, the divisor of N.
-
As total number of exponents are
(X1+1)∗(X2+1)∗....(Xi+1). -
Then if we choose P1 as K, answer should be the same product as
(X1)∗(X2+1)∗....(Xi+1).
But f[0].first will be P1 in this case.
Please clarify…
no I’m storing primes till square root of 10^9 which is in order of 1e4. I’ve tried submitting by removing the map and it worked completely fine. Map is causing the TLE, why is it so?
Nope.
For N=18=(2^1)*(3^2) and factors are (1+1)*(2+1)=6.
Here we will choose K=3 and number of factors will be (1+1)*(2)=4.
So it’s not always P1.
2 Likes
Map in C++ takes log(N) time for insert,search,delete. Hence whenever you are trying to use map you increased time by log(N) factor, so your time complexity will be O(T*sqrt(N)*log(N)). Which will not pass because we were strict with time limit.
1 Like
I tried some test cases it seems fine, I will share input and output files with you via mail, please send a hi here.
2 Likes
Check your mail and thanks for the help man :’)
time complexity in this question comes out to be O((Tsqrt(N)) which comes to be 310^7.5 which comes out to be more than 10^7 then why it is not resulting in TLE or is it 10^8 . I am pretty confuse in time complexity whether it should be 10^7 or 10^8.
You should not only consider the number of operations, but also the complexity of each operation when accounting for total execution time.
As in, 10^9 increments on an int variable can be performed in less than a fraction of a second, if the compiler is smart enough.
Like 10^7 is fine in code chef, but here it’s not always 10^7 like if you reduce N with found factors, it will be less actually.
1 Like