STRNO - Editorial

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2

Setter: Kritagya Agarwal
Tester: Felipe Mota
Editorialist: Taranpreet Singh

DIFFICULTY:

Easy

PREREQUISITES:

Number theory

PROBLEM:

Given two integers X and K, you need to determine whether there exists an integer A with exactly X factors and exactly K of them are prime numbers.

QUICK EXPLANATION

A valid choice for A exists if the prime factorization of X has the number of terms at least K. So we just need to compute prime factorization of X.

EXPLANATION

Let’s assume a valid A exists, with exactly K prime divisors.

The prime factorization of A would be like \prod_{i = 1}^K p_i^{a_i} where p_i are prime factors of A and a_i are the exponents. Then it is well known that the number of factors of A are \prod_{i = 1}^K (a_i+1). Hence we have X = \prod_{i = 1}^K (a_i+1) for a_i \geq 1, hence (a_i+1) \geq 2

So our problem is reduced to determining whether is it possible to write X as a product of K values greater than 1 or not.

For that, let us find the maximum number of values we can split X into such that each value is greater than 1. It is easy to prove that all values shall be prime (or we can further split that value). If the prime factorization of X is \prod r_i^{b_i}, then \sum b_i is the number of terms we can split X into.

For example, Consider X = 12 = 2^2*3 = 2*2*3. Hence we can decompose 12 into at most 3 values such that their product is X. However, if K < \sum b_i, we can merge the values till we get exactly K values. Suppose we have X = 12 and K = 2, so after writing 2, 2, 3, we can merge any two values, resulting in exactly two values.

So a valid A exists when the number of prime factors of X with repetition is at least K.

This decomposition can uniquely determine the exponents in the prime factorization of A, and by choosing p_i, we can find the value of A.

Bonus: Find one such value of A for specified X and K if it exists.

Bonus: Find the smallest value of A for specified X and K if it exists.

TIME COMPLEXITY

The time complexity is O(\sqrt X) per test case.

SOLUTIONS:

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

int getFactorization(ll x) 
{ 
	int cnt = 0;
	while (x%2 == 0) 
	{ 
	    cnt++;
	    x = x / 2; 
	} 
	
	for(int i = 3 ; i <= sqrt(x) ; i += 2)
	{
	    while(x%i == 0)
	    {
	        cnt++;
	        x /= i;
	    }
	}
	
	if(x > 1) cnt++;
	
	return cnt;
} 

int main(){

	int q;
	cin>>q;
	assert(q >= 1 && q <= 1000);
	while(q--){
	    int x,k;
	    cin>>x>>k;
	    assert(x >= 1 && x <= 1000000000);
	    assert(k >= 1 && k <= 1000000000);
	    int cnt = getFactorization(x);
	    if(cnt >= k) cout<<"1"<<endl;
	    else cout<<"0"<<endl;
	}
}
Tester's Solution
#include <bits/stdc++.h>
using namespace std;
template<typename T = int> vector<T> create(size_t n){ return vector<T>(n); }
template<typename T, typename... Args> auto create(size_t n, Args... args){ return vector<decltype(create<T>(args...))>(n, create<T>(args...)); }
vector<int> decompose(int x){
	vector<int> factors;
	for(int i = 2; i * i <= x; i++){
		while(x % i == 0){
			x /= i;
			factors.push_back(i);
		}
	}
	if(x > 1) factors.push_back(x);
	return factors;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int t;
	cin >> t;
	while(t--){
		int x, k;
		cin >> x >> k;
		cout << (decompose(x).size() >= k) << '\n';
	}
	return 0;
}
Editorialist's Solution
import java.util.*;
import java.io.*;
import java.text.*;
class STRNO{
	//SOLUTION BEGIN
	void pre() throws Exception{}
	void solve(int TC) throws Exception{
	    long x = nl(), k = nl();
	    long count = 0;//Sum of exponents of factorization of x
	    for(long i = 2; i*i <= x; i++){
	        if(x%i != 0)continue;
	        while(x%i == 0){
	            count++;
	            x /= i;
	        }
	    }
	    if(x > 1)count++;
	    pn(count >= k?1:0);
	}
	//SOLUTION END
	void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
	DecimalFormat df = new DecimalFormat("0.00000000000");
	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 STRNO().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;
	    }
	}
}

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

9 Likes

Detailed solution for April Long Challenge.

5 Likes

#include <bits/stdc++.h>
using namespace std;
long long int k;
void prime_power_count(long long int n);
void sieveOfEratosthenes(long long int n,long long int s[]);
int main() {
long long int t,x;
scanf("%lli",&t);
while(t–){
scanf("%lli %lli",&x,&k);
prime_power_count(x);
}
return 0;
}
void prime_power_count(long long int n){
long long int s[n+1],signal=0;
sieveOfEratosthenes(n, s);
long long int curr=s[n];
long long int cnt=0;
while(n>1){
n=n/s[n];
cnt++;
curr=s[n];
if(cnt>=k){
signal=1;
break;}
}
if(signal==1)
printf(“1\n”);
else
printf(“0\n”);
}
void sieveOfEratosthenes(long long int N, long long int s[])
{
// Create a boolean array “prime[0…n]” and
// initialize all entries in it as false.
vector prime(N+1, false);

// Initializing smallest factor equal to 2 
// for all the even numbers 
for (long long int i=2; i<=N; i+=2) 
    s[i] = 2; 

// For odd numbers less then equal to n 
for (long long int i=3; i<=N; i+=2) 
{ 
    if (prime[i] == false) 
    { 
        // s(i) for a prime is the number itself 
        s[i] = i; 

        // For all multiples of current prime number 
        for (long long int j=i; j*i<=N; j+=2) 
        { 
            if (prime[i*j] == false) 
            { 
                prime[i*j] = true; 

                // i is the smallest prime factor for 
                // number "i*j". 
                s[i*j] = i; 
            } 
        } 
    } 
} 

}
any ideas to optimize this code

You can refer to setter’s/editorial’s/tester’s solution all of them are optimized and easy to understand. Also you can look at the following simple code

for _ in range(int(raw_input())):
    x,k = map(int,raw_input().split())
    cnt = 0; i = 2
    while i*i <= x:
        while x%i==0:
            x //= i
            cnt += 1
        i += 1
    if x>1:
        cnt += 1

    if k<=cnt:
        print(1)
    else:
        print(0)
1 Like

Here are a couple of filters that can be added to get O(1) solution for certain cases:

  • For any given K; if X < 2K the result is always 0.
  • A direct result of this is, since X<=109; If k>=30, the result will always be 0 irrespective of the value of X.
2 Likes

My solution worked on my pc , but when i ran it on codechef, it printed out only 0s.
Can someone please help me?

Link to my code - CodeChef: Practical coding for everyone

Thanks.

1 Like

problem is here

if (check==0)
{
    check=1;
}

if(check>=k)        // use elseif
{
    cout<<"1"<<endl;
}

I had a solution if x is the no of total factors and k is the prime factors so we know that x will always have 1 as a factor and if(x-1>=k) then there will always exist a no example 2 x will be 2(1,2) and k will be 1 (2) and x = 3(1,7,49) and k will be 1(7) can anyone tell me what is wrong in this

My commented code for the solution.

@mlango you are right but can anyone figure out why my code passed only test case 1
see this:

For the setter’s solution(or tester’s solution also), can somebody explain why is he only counting prime factors till square root. Prime factorization can go even further than that, right?

Example 10000. Prime factorization goes even beyond 100, you will get primes even beyond that, so why is he only considering till square root?

i don’t think so. There are only two prime factors. 2 and 5. both are less than 100.
There is only one case when prime factors is > sqrt(n). When the number is prime itself.

2 Likes

Maybe I didn’t understand the solution correctly,then.As far as I know,we are getting prime factors of X,and if they are equal to or more then K,then answer is yes.
Now when we check for prime factors,we should try to get all of them,right?

Like 144 for example.The solution only checks till square root,12. But won’t we find any primes that divide 144 after the square root? Now in 144’s case,we won’t find any primes after 12 that divide 144. But what if a number exists like that? Or maybe I am forgetting some fundamental maths here.

1 Like

You will check for 2, Since 2 divides it, find how many time will it divide 144,

2^4 is the highest power of 2 which divides 144, count = 4
144/16 = 9 , check 3, 3^2 divides 9, count = 4+2 = 6
Now if 6>=k ans is yes otherwise No.

You can use for/while loop to check highest power which divides given number.

2 Likes

I understood that part bro. I am not getting why we won’t get prime factors for a number after the square root.It’s more of a mathematical question to me now.I couldn’t run this code in the challenge itself,just because of this reason.

If there is a factor beyond sqrt(n) then its power will be 1 ( n < (sqrt(n)+k)*(sqrt(n)+k) )
You can divide all factors less than sqrt(n) and what you will be left with is just a number>1 which itself is a prime factor.
For example lets take 14,
sqrt(14) = 3 ,
14/2 = 7
Now it doesn’t get divided by 3.
Check this : Efficient program to print all prime factors of a given number
Hence we can conclude that 7 is prime factor.

3 Likes

That along with the article made it clear.Thanks.

1 Like

what is the reasoning behind this logic? Fairly simple without finding prime factors !

this problem is all related to observation and nothing else.

which numbers we can directly say are not coprime without even thinking ? these are even numbers.

this is itself the solution dear.
And we have to print n/2 lines ofcourse because we have n/2 even numbers in the range of [ 1,n ], just prime 2 numbers in each line consecutively and in the case where n is odd print 3 numbers in the last or first line.

Thats it.