DIVISOR - Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Practice

Setter: Smit Mandavia
Tester: Istvan Nagy
Editorialist: Taranpreet Singh

DIFFICULTY

Medium

PREREQUISITES

Pre-computation, Prime sieve and a bit of number theory.

PROBLEM

Given a number N, you are allowed to make the following operation any number of times.

  • Choose a number K such that K has exactly four divisors, divide N by K.

You want to minimize the number of factors of N. 1 \leq N \leq 10^6

QUICK EXPLANATION

  • Since for all K, N/K < N, so we can compute the answer for each N from 1 to N, using previous answers.
  • For current N, we can make a list of its divisors having exactly four factors. We can also precompute the number of divisors of each number.
  • We can check for each candidate the best answer, the one leading to minimum number of divisors.

EXPLANATION

Since there are 10^6 values of N, we can precompute the answer for each N and then print them out.

First of all, some basic number theory class.
Number of factors of a number
If number N = \prod p_i^{a_i} where p_i are distinct primes, then the number of divisors of N is \prod (1+a_i)

Why?

Letā€™s assume N has K distinct prime factors. Consider an int vector b with K entries, where 0 \leq b_i \leq a_i. We can see that each such vector correspond to exactly one factor of N. i-th value can take (1+a_i) different values, and values at each position are independent, so the number of possible vectors b is \prod (1+a_i)

Read in detail here

Making list of factors of all numbers up to N can be done in two ways.

  • Factoring each number individually (slower)
    This way, weā€™d spend O(\sqrt x ) time factoring x
  • Considering multiples of all values from 1 to N.
    This way, we consider each number v one by one, and iterate over its multiples k*v. All multiples of v definitely have v has a factor.
    The time complexity of this approach is N+N/2+N/3 \ldots N/N = N*(1+1/2+1/3 \ldots 1/N) which is roughly O(N*log(N))

Hence, now we have number of factors of a number as well as the list of factors of each number 1 \leq n \leq N.

Now, an important thing to observe here is how N changes.

Letā€™s consider N = 216 = 2^3 * 3^3. The factors of 216 having exactly 4 divisors are 6, 8 and 27. Considering each K one by one, we can replace N = 216 with 36, 27 or 8.

Assuming D_n denotes the number of divisors of N, and A_n denote the minimum number of divisors of N after applying any number of operations, then we can say that A_n = min(D_n, min_{A_{n/k}}) where k is a factor of N with exactly four divisors. D_n denotes not performing operation at all, hence the required number of divisors is the number of divisors of N in that case.

Since we have A_m already computed for all m < n, and we also have D_n, we can easily compute this.

For N = 216, A_{216} = min(D_{216}, min(A_{36}, A_{27}, A_{8})). All values D_{216}, A_{36}, A_{27} and A_{8} are already computed, hence A_{216} is computed.

Do have a look at setterā€™s solution, if looking for neat implementation.

An alternative way of approaching (Not part of above solution)

As it happens, we didnā€™t use the fact of number having exactly four divisors at all. A number have exactly four divisors in following cases.

  • The number is product of two primes p and q where p \neq q
  • The number is of form p^3 for some prime p

So if we write the prime factorization of N = \prod p_i^{a_i}, try noticing what impact does dividing by K have on factorization of N.

If K = p_i*p_j , it reduces a_i and a_j by one. If K = p_i^3, then it reduces a_i by 3.

Hence, considering only list a, the problem is reduced into following.

Given a list of values a, you are allowed to reduce two distinct elements by one, or reduce any element by 3. You can perform any operation any number of times. Determine the minimum value of product \prod (1+a_i) after applying operations optimally.

Can anyone figure out a decent approach on how to solve this? Do comment. Have fun as always!

TIME COMPLEXITY

The time complexity is O(MX*log(MX)+T) where MX = 10^6.
The space complexity is O(MX) or O(MX*log(MX)), depending upon implementation.

SOLUTIONS

Setter's Solution
#include<bits/stdc++.h>
using namespace std;
 
#define ll long long int
#define FIO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define mod 1000000007
#define N 1000000
 
int main(){
    FIO;
            
    int i,j;
    int numOfDivisors[N+1]={0};
    int ans[N+1]={0};
    
    for(i=1;i<=N;i++)
        for(j=i;j<=N;j+=i){
            numOfDivisors[j]++;
            ans[j]++;
        }
    
    for(i=1;i<=N;i++)
        for(j=i;j<=N;j+=i)
            if(numOfDivisors[j/i]==4)
                ans[j] = min(ans[j], ans[i]);
 
    cin >> i;
    while(i--){
        cin >> j;
        cout << ans[j] << "\n";
    }
    
    return 0;
}
Tester's Solution
#include <iostream>
#include <cassert>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <random>
#include <limits>
#include <unordered_map>
#include <numeric>
#include <functional>

#ifdef HOME
#define NOMINMAX   
#include <windows.h>
#endif

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)

template<class T> bool umin(T& a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool umax(T& a, T b) { return a < b ? (a = b, true) : false; }

using namespace std;

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) {
		    assert(cnt > 0);
		    if (is_neg) {
			    x = -x;
		    }
		    assert(l <= x && x <= r);
		    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;
	    }
	    // 		if(g == '\r')
	    // 			continue;

	    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, ' ');
}

int main(int argc, char** argv)
{
#ifdef HOME
    if (IsDebuggerPresent())
    {
	    freopen("../DIVISOR_0.in", "rb", stdin);
	    freopen("../out.txt", "wb", stdout);
    }
#endif
    int T = readIntLn(1, 1'000'000);
    vector<vector<int>> v(1'000'002);
    vector<int> p(1'000'002,1);
    vector<int> r(1'000'002);
    fore(i, 2, 1'000'001)
    {
	    if (p[i] == 1)
	    {
		    for (int j = i; j < v.size(); j += i)
		    {
			    p[j] = 0;
			    int tmp = j;
			    int ctr = 0;
			    while (tmp % i == 0)
			    {
				    ++ctr;
				    tmp /= i;
			    }
			    v[j].push_back(ctr);
		    }
	    }
    }

    map<vector<int>, int> sol;

    fore(i, 2, 1'000'001)
    {
	    sort(v[i].begin(), v[i].end(), std::greater<int>());
	    if (sol.count(v[i]))
	    {
		    r[i] = sol[v[i]];
		    continue;
	    }
	    if (v[i].size() == 1)
	    {
		    sol[v[i]] = 1 + v[i][0] % 3;
	    }
	    else
	    {
		    int bestSol = std::accumulate(v[i].begin(), v[i].end(), 0);
		    forn(j, v[i].size())
		    {
			    if (v[i][j] > 2)
			    {
				    auto w = v[i];
				    w[j] -= 3;
				    sort(w.begin(), w.end(), std::greater<int>());
				    while (w.back() == 0)
					    w.pop_back();
				    bestSol = min(bestSol, sol[w]);
			    }
		    }
		    forn(j, v[i].size())
		    fore(k, j + 1, v[i].size() - 1)
		    {
			    auto w = v[i];
			    w[j]--; w[k]--;
			    sort(w.begin(), w.end(), std::greater<int>());
			    while (w.size() && w.back() == 0)
				    w.pop_back();
			    if (w.empty())
				    bestSol = 1;
			    else
				    bestSol = min(bestSol, sol[w]);
		    }
		    sol[v[i]] = bestSol;
	    }
	    r[i] = sol[v[i]];
    }
    r[1] = 1;
    forn(tc, T)
    {
	    int N = readIntLn(1, 1'000'000);
	    printf("%d\n", r[N]);
    }
    assert(getchar() == -1);
    return 0;
}
Editorialist's Solution
import java.util.*;
import java.io.*;
class DIVISOR{
    //SOLUTION BEGIN
    int MX = (int)1e6;
    int[] ans;
    void pre() throws Exception{
        ans = new int[1+MX];
        int[] spf = spf(MX);
        int[] divisorCount = new int[1+MX];
        for(int i = 1; i<= MX; i++)divisorCount[i] = countFactors(spf, i);
        ArrayList<Integer>[] factors = new ArrayList[1+MX];
        for(int i = 1; i<= MX; i++)factors[i] = new ArrayList<>();
        for(int i = 1; i<= MX; i++){
            if(divisorCount[i] == 4)
                for(int j = i; j<= MX; j += i)
                    factors[j].add(i);
        }
        for(int i = 1; i<= MX; i++){
            ans[i] = divisorCount[i];
            for(int x:factors[i])if(divisorCount[x] == 4 && ans[i/x] < ans[i])ans[i] = ans[i/x];
        }
    }
    void solve(int TC) throws Exception{
        pn(ans[ni()]);
    }
    int[] spf(int max){
        int[] spf = new int[1+max];
        for(int i = 2; i<= max; i++)
            if(spf[i] == 0)
                for(int j = i; j <= max; j += i)
                    if(spf[j] == 0)
                        spf[j] = i;
        return spf;
    }
    int countFactors(int[] spf, int x){
        int count = 1;
        while(x > 1){
            int p = spf[x], cnt = 0;
            for(;x%p == 0; x/= p)cnt++;
            count *= 1+cnt;
        }
        return count;
    }
    //SOLUTION END
    void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
    static boolean multipleTC = true;
    FastReader in;PrintWriter out;
    void run() throws Exception{
        in = new FastReader();
        out = new PrintWriter(System.out);
        //Solution Credits: Taranpreet Singh
        int T = (multipleTC)?ni():1;
        pre();for(int t = 1; t<= T; t++)solve(t);
        out.flush();
        out.close();
    }
    public static void main(String[] args) throws Exception{
        new DIVISOR().run();
    }
    int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
    void p(Object o){out.print(o);}
    void pn(Object o){out.println(o);}
    void pni(Object o){out.println(o);out.flush();}
    String n()throws Exception{return in.next();}
    String nln()throws Exception{return in.nextLine();}
    int ni()throws Exception{return Integer.parseInt(in.next());}
    long nl()throws Exception{return Long.parseLong(in.next());}
    double nd()throws Exception{return Double.parseDouble(in.next());}

    class FastReader{
        BufferedReader br;
        StringTokenizer st;
        public FastReader(){
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public FastReader(String s) throws Exception{
            br = new BufferedReader(new FileReader(s));
        }

        String next() throws Exception{
            while (st == null || !st.hasMoreElements()){
                try{
                    st = new StringTokenizer(br.readLine());
                }catch (IOException  e){
                    throw new Exception(e.toString());
                }
            }
            return st.nextToken();
        }

        String nextLine() throws Exception{
            String str = "";
            try{   
                str = br.readLine();
            }catch (IOException e){
                throw new Exception(e.toString());
            }  
            return str;
        }
    }
}

VIDEO EDITORIAL:

Feel free to share your approach. Suggestions are welcomed as always. :slight_smile:

4 Likes

In the contest, I thought of the alternate approach mentioned in the editorial. But couldnā€™t figure the best reduction approachā€¦ Nice way to end the tutorial :wink:

5 Likes

Same, I also want to know that best reduction approach of alternative method.

Guess what, even I wanna know it @code_123_45 and @zakir_ahmed :stuck_out_tongue:
PS: I am the setter

3 Likes

lol

1 Like

is there any approach for the alternate solution I tried with one greedy approach but I got a WA :frowning:

I couldnā€™t find any except brute force recursion with memoization which is essentially same as solution 1.

I have used the same approch as given in alternate solution but I get WA .
Can anyone please help me where is mistake
My implementation
https://www.codechef.com/viewsolution/43233050

1 Like

What about this. I wonder why itā€™s not working.
The logic is same as above:
k is in the form of p_1 *p_2 or p^3
So I got all the powers of primes. Now I can always use p^3 so did %3 on each a_i
Now some 2ā€™s and 1ā€™s will be present. Any pair of 2ā€™s or pair of 1ā€™s can be reduced to zeroes. Weā€™ll be left with at most one 2 and at most one 1 and casework.
Edit: as @watergun pointed out this wonā€™t work

What if we are left with
2 2 2
All of these can be paired to get 1 as the result, right?

1 Like

Yes there are so many cases.
Now that you have correct solution which can work upto 10^6, you can check when answer is 3 or 2 and try to find some observation or pattern. This might lead to a better solution.

So the problem somewhat reduces to:
Given an array find the min number you can get if you can subtract 3 from an element or subtract 1 from 2 different elements! Is there a dp or any other approach to solve this as i canā€™t come up with anything?

I tried greedy approach but it didnā€™t work but I donā€™t know why it is not working (as I manually couldnā€™t find a test case failing this code). can anyone help me please?

/*
	ą„
		JAI SHREE RAM

		Hare Krishna Hare Krishna Krishna Krishna Hare Hare
		Hare Rama Hare Rama Rama Rama Hare Hare
	
												ą„
*/

//Written by Bhuwanesh Nainwal
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
pbds;



#define fast            	ios_base::sync_with_stdio(false) , cin.tie(NULL) , cout.tie(NULL)
#define int					long long int
#define vci              	vector<int>
#define vcvci             	vector<vector<int>>
#define vcpi             	vector<pair<int,int>>
#define vcs					vector<string>
#define pb              	push_back
#define mpii             	map<int , int>
#define mpsi             	map<string , int>
#define mpci             	map<char , int>
#define umpii             	unordered_map<int , int>
#define umpsi             	unordered_map<string , int>
#define umpci             	unordered_map<char , int>
#define all(x)				auto it = x.begin() ; it != x.end() ; it++
#define vcc              	vector<char>
#define vcs              	vector<string>
#define sti            		set<int>
#define stc            		set<char>
#define sts            		set<string>
#define pqmx				priority_queue<int>
#define pqmn				priority_queue<int , vi , greater<int>>
#define null            	NULL
#define ff            		first
#define ss              	second
#define stb(x)				__builtin_popcount(x)
#define lzr(x)				__builtin_clz(x)
#define tzr(x)					__builtin_ctz(x)
#define prc(x , y)          fixed << setprecision(y) << x
#define max3(a, b, c)   	max(a, max(b, c))
#define min3(a, b, c)   	min(a, min(b, c))

using namespace std;

const int mod = 1e9 + 7;
const int INF = 1e9;
const int LINF = 1e18;
const int N = 1e6 + 10;
const int chkprc = 1e-9;  // Check for precision error in double


vector<bool> is_prime(N + 1, 0);
vector<int> primes;
void sieve()
{    
    is_prime[2] = 1;
    primes.pb(2);
    for(int i = 3 ; i <= N ; i += 2)
        is_prime[i] = 1;
    for(int i = 3 ; i <= N ; i += 2)
    {
        if(is_prime[i])
        {
            primes.pb(i);
            for(int j = i * i ; j <= N ; j += i)
                    is_prime[j] = 0;
        }
    }
}
int prime_factorization(int n)
{
    int total = 0;
    int distinct = 0;
    for(int i = 0 ; i < primes.size() ; i++)
    {
        if(primes[i] * primes[i] > n)
            break;
        if(n % primes[i] == 0)
        {
            int cnt = 0;
            while(n % primes[i] == 0)
            {
                n = n / primes[i];
                cnt++;
            }
            if(cnt % 3 != 0)
            {
                total += (cnt % 3);
                distinct++;
            }    
        }   
    }
    if(n > 1)
    {
        total ++;
        distinct++;
    }
  
    if(distinct == 1 && total == 2)
        return 3;
    if(total % 2 == 0)
        return 1;
    return 2;   
}



void solve()
{
    int n;
    cin >> n;
    cout << prime_factorization(n) << "\n";

}

void local()
{
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif // ONLINE_JUDGE
}

int32_t main()
{

    fast;
    sieve();
    // local();
    int T = 1;
    cin>>T;

    while(T--)
    {
        solve();
    }

    return 0;
}

i donā€™t get this . anyone please explain it

A_n: Answer for n
D_n: Number of divisors of N
A_n = min(D_n, A_{n/k}) for all k being factors of N and having 4 divisors.

1 Like

Couple of facts about alternate solution

  • With N upto 10^9, thereā€™d be atmost 8 elements. The maximum value in A is also not so large.
  • if max(A)*2 \leq sum(A), then we can reduce A to all zeros, or all zeros and one 1 using only first operation.
  • In the end, there would be only one non-zero element, which would either be 0, 1 or 2.
  • Even backtracking can give good results, considering very few elements.

I believe I have a solution, but since I havenā€™t tested it on tests nor having proven it, I cannot be sure. Nor do I want to spoil the fun :stuck_out_tongue:

2 Likes

Hi,
I could come up with this solution for the alternate approach to reduce the powers.
a) Reduced all the powers taking modulo 3 and kept track of the reductions.
b) Now the power array has only 0,1,2. We are only interested in the reduction of 1 and 2s and thats obvious.
The reduction was based on below observations.

  1. Even number of 1ā€™s can be reduced to 0.
  2. If the powers array has both 1ā€™s and 2ā€™s, the 2ā€™s can be reduced and the same number of ones remain because, if we combine 1 and 2, 1 vanishes and 2 converts to 1. So, if we have even 1ā€™s, irrespective of number of 2ā€™s can be reduced to 0.
  3. If we have only 2ā€™s more than 1, can be reduced to 0. If there is only one single 2, it cannot be reduced.
  4. So we only investigate the cases for reduction (using the modulo 3 reductions tracked), a) Where we have odd number of ones. b) Where we have a single power 2.
  5. Important: If the reductions are at more than 3 places, the above 2 cases reduce to 0.
    a) Where we have odd number of ones. Explanation: We can use a single 1 and pair with 9 available powers from 3 reductions. This leaves with 8 powers which can be paired and reduced to 0. Now if you see the number of ones also became even.
    b) Where we have a single power 2. Explanation: We can pair this 2 with 2 powers( from 2 reductions), that leaves with 4 powers which can be reduced to 0 and original single 2 also vanished.
    So, we only investigate above cases when reductions are 1 or 2.

I know this is a bit adhoc and haphazard. Appreciate if there is a simpler and better solution.

https://www.codechef.com/viewsolution/43283305

1 Like

To help me understand better, kindly explain with an example, say if powers are 5,3,1. Thanks

Just an idea, You may pick one AC solution and compute solution for first 1000 numbers and then compare with your solution to see the mismatches. This might help to figure out the issue if any.

is there even a case when answer is 3?

waiting for your response.