# MXFACS - Editorial

Maximum Factors Problem:

Practice

Code Drive Contest Division 1

Code Drive Contest Division 2

Code Drive Contest Division 3

Author: Sobhagya Singh Dewal
Tester: Lavish Gupta , Takuki Kurokawa

EASY

Greedy, Math

# PROBLEM:

You are given an integer N. Let K be a divisor of N of your choice such that K > 1, and let M = \frac{N}{K}. You need to find the smallest K such that M has as many divisors as possible.

Note: U is a divisor of V if V is divisible by U.

# QUICK EXPLANATION:

Find prime factorization of the number N, the smallest prime with maximum frequency will be the answer.
For example let’s say prime factorization of N is P_{1}^{X_{1}}*P_{2}^{X_{2}}......P_{i}^{X_{i}}
Minimum P with Maximum X value will be the answer.

# EXPLANATION:

We know that N can be written in the form
N=P_{1}^{X_{1}}*P_{2}^{X_{2}}......P_{i}^{X_{i}}
where P_{1},P_{2}....P_{i} are primes and
X_{1},X_{2}....X_{i} are their respective exponents.

Now, the number of factors of N will be
(X_{1}+1)*(X_{2}+1)*....(X_{i}+1).

We want to divide N by it’s one of the factor such that remaining number has maximum number of factors so it is always optimal to reduce maximum X_{i} by one, means we will divide N by one of it’s factor which have maximum exponent, so first we will find the maximum exponent and then will choose minimum prime with maximum exponent.
Time Complexity: O(\sqrt N) for each testcase.

# SOLUTIONS:

Setter’s Solution
#include <bits/stdc++.h>
#define int long long int
using namespace std;

int f(int n)
{
int cur = 0, ans = n;
int cnt = 0;
while (n % 2 == 0)
{
n /= 2;
cnt++;
}
if (cnt > cur)
{
ans = 2;
cur = cnt;
}
for (int i = 3; i * i <= n; i += 2)
{
cnt = 0;
while (n % i == 0)
{
n /= i;
cnt++;
}
if (cnt > cur)
{
ans = i;
cur = cnt;
}
}
if (n > 1)
{
if (1 > cur)
{
ans = n;
cur = 1;
}
}
return ans;
}
void myfun()
{
int n;
cin >> n;
cout << f(n) << "\n";
}

signed main()
{
int t = 1;
cin >> t;
for (int tt = 1; tt <= t; tt++)
{
myfun();
}
return 0;
}

Tester's (Lavish Gupta) Solution
// O(N^1/2 * T)
#include <bits/stdc++.h>
using namespace std;
#define ll long long

/*
------------------------Input Checker----------------------------------
*/

long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);

assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
if(is_neg){
x= -x;
}

if(!(l <= x && x <= r))
{
cerr << l << ' ' << r << ' ' << x << '\n';
assert(1 == 0);
}

return x;
} else {
assert(false);
}
}
}
string ret="";
int cnt=0;
while(true){
char g=getchar();
assert(g!=-1);
if(g==endd){
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt && cnt<=r);
return ret;
}
long long readIntSp(long long l,long long r){
}
long long readIntLn(long long l,long long r){
}
}
}

/*
------------------------Main code starts here----------------------------------
*/

const int MAX_T = 3000;
const int MAX_N = 1000000000;
const int MAX_SUM_N = 100000;

#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)

int sum_n = 0;
int max_n = 0;
int yess = 0;
int nos = 0;
int total_ops = 0;
ll z = 1000000007;
ll sum_nk = 0 ;

int get_facts(int n)
{
ll cnt = 0 ;
// cout << "n = " << n << endl ;
for(ll i = 1 ; i*i <= n ; i++)
{
if(n%i == 0)
{
cnt++ ;
if(n != i*i)
cnt++ ;
}
}
return cnt ;
}

void solve()
{
int n = readIntLn(1 , MAX_N) ;
ll a = n ;
int ans = n , facts = 0 ;
vector<pair<int , int> > v ;
int max_cnt = 0 ;

for(int i = 2 ; i*i <= n ; i++)
{
if(n%i == 0)
{
int cnt = 0 ;
while(n%i == 0)
{
cnt++ ;
n /= i ;
}
v.push_back({i , cnt}) ;
max_cnt = max(max_cnt , cnt) ;
}
}
if(n > 1)
{
max_cnt = max(max_cnt , 1) ;
v.push_back({n , 1}) ;
}

for(int i = 0 ; i < v.size() ; i++)
if(v[i].second == max_cnt)
ans = min(ans , v[i].first) ;

cout << ans << '\n' ;
return ;
}

signed main()
{
//fast;
#ifndef ONLINE_JUDGE
freopen("inputf.txt" , "r" , stdin) ;
freopen("outputf.txt" , "w" , stdout) ;
freopen("error.txt" , "w" , stderr) ;
#endif

int t = 1;

for(int i=1;i<=t;i++)
{
solve() ;
}

assert(getchar() == -1);
// assert(sum_n <= MAX_SUM_N);

cerr<<"SUCCESS\n";
cerr<<"Tests : " << t << '\n';
// cerr<<"Sum of lengths : " << sum_n << '\n';
// cerr<<"Maximum length : " << max_n << '\n';
// cerr << "Sum of product : " << sum_nk << '\n' ;
// cerr<<"Total operations : " << total_ops << '\n';
// cerr<<"Answered yes : " << yess << '\n';
// cerr<<"Answered no : " << nos << '\n';
}

Tester's (Takuki Kurokawa) Solution
#include <bits/stdc++.h>
using namespace std;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int tt;
cin >> tt;
while (tt--) {
int n;
cin >> n;
vector<pair<int, int>> f;
for (int i = 2; i * i <= n; i++) {
if (n % i == 0) {
f.emplace_back(i, 0);
while (n % i == 0) {
n /= i;
f.back().second++;
}
}
}
if (n) {
f.emplace_back(n, 1);
}
sort(f.begin(), f.end(), [&](auto x, auto y) {
if (x.second == y.second) {
return x.first < y.first;
}
return x.second > y.second;
});
cout << f[0].first << '\n';
}
return 0;
}

4 Likes

The maximum count of a prime factor was pretty trivial, good problem!

First I thought answer will be smallest prime factor of n and got the WA verdict. I corrected it then. But I am still unable to find any n for which answer will not be its smallest prime factor. Can anyone give an example of such case ? @manoj_vajpeyi

1 Like

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

I am getting wrong answer for my submission, can someone pls point any failing test case.

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

can someone help
why am getting WA?

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.

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?

I am getting wrong answer for my submission, can someone pls point any failing test case.

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 :’)