MXFACS - Editorial

Maximum Factors Problem:

PROBLEM LINK:

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

DIFFICULTY:

EASY

PREREQUISITES:

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 readString(int l,int r,char endd){
    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){
    return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
    return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
    return readString(l,r,'\n');
}
string readStringSp(int l,int r){
    return readString(l,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;
    
    t = readIntLn(1,MAX_T);

    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.

@manoj_vajpeyi please help with my query, why is map giving TLE

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?
sol link: https://www.codechef.com/submit/complete/55659105

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?

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