# STRNO - Editorial

**URL:** <https://discuss.codechef.com/t/strno-editorial/61191>\
**Category:** editorial\
**Tags:** easy, editorial, number-theory, taran\_1407, april20\
**Created:** [April 10, 2020, 12:14am UTC](https://discuss.codechef.com/t/strno-editorial/61191 "2020-04-10T00:14:26Z")\
**Posts on this page:** 20\
**Page:** 1

<div class="post-metadata">

**Author:** ![taran\_1407](https://discuss.codechef.com/user_avatar/discuss.codechef.com/taran_1407/32/299985_2.png) [@taran\_1407](https://discuss.codechef.com/u/taran_1407)\
**Post date:** [April 10, 2020, 12:14am UTC](https://discuss.codechef.com/t/strno-editorial/61191/1 "2020-04-10T00:14:26Z")

</div>

# PROBLEM LINK:

[Practice](https://www.codechef.com/problems/STRNO)  
[Contest: Division 1](https://www.codechef.com/APRIL20A/problems/STRNO)  
[Contest: Division 2](https://www.codechef.com/APRIL20B/problems/STRNO)

**Setter:** [Kritagya Agarwal](https://www.codechef.com/users/krikti)  
**Tester:** [Felipe Mota](https://www.codechef.com/users/fmota)  
**Editorialist:** [Taranpreet Singh](https://www.codechef.com/users/taran_1407)

# 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](https://www.wikihow.com/Find-How-Many-Factors-Are-in-a-Number) 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;
> }
> }
> 
> ```

[details = “Tester’s Solution”]  
#include \<bits/stdc++.h\>  
using namespace std;  
template vector create(size\_t n){ return vector(n); }  
template\<typename T, typename… Args\> auto create(size\_t n, Args… args){ return vector\<decltype(create(args…))\>(n, create(args…)); }  
vector decompose(int x){  
vector 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;  
}  
[/details]  
[details = “Editorialist’s Solution”]  
import java.util._;  
import [java.io](http://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;
	    }
	}
}

```

[/details]

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

---

<div class="post-metadata">

**Author:** ![ishita\_gupta](https://discuss.codechef.com/user_avatar/discuss.codechef.com/ishita_gupta/32/3653_2.png) [@ishita\_gupta](https://discuss.codechef.com/u/ishita_gupta)\
**Post date:** [April 13, 2020, 12:27pm UTC](https://discuss.codechef.com/t/strno-editorial/61191/2 "2020-04-13T12:27:15Z")

</div>

Detailed solution for April Long Challenge.

> **[CodeChef April Long Challenge Solution (Div 2)](https://medium.com/@manthangupta109/codechef-april-long-challenge-solution-div-2-cc0b05c9cbfe)**
>
> Overly Simplified

---

<div class="post-metadata">

**Author:** ![anon59437178](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@anon59437178](https://discuss.codechef.com/u/anon59437178)\
**Post date:** [April 13, 2020, 12:58pm UTC](https://discuss.codechef.com/t/strno-editorial/61191/3 "2020-04-13T12:58:35Z")

</div>

#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

---

<div class="post-metadata">

**Author:** ![nagesh\_reddy](https://discuss.codechef.com/user_avatar/discuss.codechef.com/nagesh_reddy/32/208394_2.png) [@nagesh\_reddy](https://discuss.codechef.com/u/nagesh_reddy)\
**Post date:** [April 13, 2020, 1:38pm UTC](https://discuss.codechef.com/t/strno-editorial/61191/4 "2020-04-13T13:38:10Z")

</div>

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

```auto
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)
```

---

<div class="post-metadata">

**Author:** ![mlango](https://discuss.codechef.com/user_avatar/discuss.codechef.com/mlango/32/3653_2.png) [@mlango](https://discuss.codechef.com/u/mlango)\
**Post date:** [April 13, 2020, 2:13pm UTC](https://discuss.codechef.com/t/strno-editorial/61191/5 "2020-04-13T14:13:31Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![ayonsen](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@ayonsen](https://discuss.codechef.com/u/ayonsen)\
**Post date:** [April 13, 2020, 3:09pm UTC](https://discuss.codechef.com/t/strno-editorial/61191/6 "2020-04-13T15:09:10Z")

</div>

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](https://www.codechef.com/viewsolution/31569548)

Thanks.

---

<div class="post-metadata">

**Author:** ![udit043](https://discuss.codechef.com/user_avatar/discuss.codechef.com/udit043/32/67897_2.png) [@udit043](https://discuss.codechef.com/u/udit043)\
**Post date:** [April 13, 2020, 9:52pm UTC](https://discuss.codechef.com/t/strno-editorial/61191/7 "2020-04-13T21:52:55Z")

</div>

problem is here

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

---

<div class="post-metadata">

**Author:** ![klakho](https://discuss.codechef.com/user_avatar/discuss.codechef.com/klakho/32/3653_2.png) [@klakho](https://discuss.codechef.com/u/klakho)\
**Post date:** [April 14, 2020, 5:57am UTC](https://discuss.codechef.com/t/strno-editorial/61191/9 "2020-04-14T05:57:45Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![sourabhbadhya](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@sourabhbadhya](https://discuss.codechef.com/u/sourabhbadhya)\
**Post date:** [April 14, 2020, 6:48am UTC](https://discuss.codechef.com/t/strno-editorial/61191/10 "2020-04-14T06:48:40Z")

</div>

My commented code for the solution.

> <https://github.com/SourabhBadhya/Codechef-problems-and-solutions/blob/master/STRNO.cpp>

---

<div class="post-metadata">

**Author:** ![krishan12345](https://discuss.codechef.com/user_avatar/discuss.codechef.com/krishan12345/32/11737_2.png) [@krishan12345](https://discuss.codechef.com/u/krishan12345)\
**Post date:** [April 14, 2020, 10:59am UTC](https://discuss.codechef.com/t/strno-editorial/61191/11 "2020-04-14T10:59:19Z")

</div>

@mlango you are right but can anyone figure out why my code passed only test case 1  
[see this:](https://www.codechef.com/viewsolution/31367839)

---

<div class="post-metadata">

**Author:** ![titichh51477](https://discuss.codechef.com/user_avatar/discuss.codechef.com/titichh51477/32/19509_2.png) [@titichh51477](https://discuss.codechef.com/u/titichh51477)\
**Post date:** [April 15, 2020, 6:33am UTC](https://discuss.codechef.com/t/strno-editorial/61191/12 "2020-04-15T06:33:06Z")

</div>

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?

---

<div class="post-metadata">

**Author:** ![l\_returns](https://discuss.codechef.com/user_avatar/discuss.codechef.com/l_returns/32/233293_2.png) [@l\_returns](https://discuss.codechef.com/u/l_returns)\
**Post date:** [April 15, 2020, 6:51am UTC](https://discuss.codechef.com/t/strno-editorial/61191/13 "2020-04-15T06:51:54Z")

</div>

> [@titichh51477](#):
>
> Prime factorization goes even beyond 100

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.

---

<div class="post-metadata">

**Author:** ![titichh51477](https://discuss.codechef.com/user_avatar/discuss.codechef.com/titichh51477/32/19509_2.png) [@titichh51477](https://discuss.codechef.com/u/titichh51477)\
**Post date:** [April 15, 2020, 11:51am UTC](https://discuss.codechef.com/t/strno-editorial/61191/14 "2020-04-15T11:51:58Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![l\_returns](https://discuss.codechef.com/user_avatar/discuss.codechef.com/l_returns/32/233293_2.png) [@l\_returns](https://discuss.codechef.com/u/l_returns)\
**Post date:** [April 15, 2020, 11:56am UTC](https://discuss.codechef.com/t/strno-editorial/61191/15 "2020-04-15T11:56:20Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![titichh51477](https://discuss.codechef.com/user_avatar/discuss.codechef.com/titichh51477/32/19509_2.png) [@titichh51477](https://discuss.codechef.com/u/titichh51477)\
**Post date:** [April 15, 2020, 12:03pm UTC](https://discuss.codechef.com/t/strno-editorial/61191/16 "2020-04-15T12:03:44Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![l\_returns](https://discuss.codechef.com/user_avatar/discuss.codechef.com/l_returns/32/233293_2.png) [@l\_returns](https://discuss.codechef.com/u/l_returns)\
**Post date:** [April 15, 2020, 12:08pm UTC](https://discuss.codechef.com/t/strno-editorial/61191/17 "2020-04-15T12:08:59Z")

</div>

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](https://www.geeksforgeeks.org/print-all-prime-factors-of-a-given-number/)  
Hence we can conclude that 7 is prime factor.

---

<div class="post-metadata">

**Author:** ![titichh51477](https://discuss.codechef.com/user_avatar/discuss.codechef.com/titichh51477/32/19509_2.png) [@titichh51477](https://discuss.codechef.com/u/titichh51477)\
**Post date:** [April 15, 2020, 12:21pm UTC](https://discuss.codechef.com/t/strno-editorial/61191/18 "2020-04-15T12:21:30Z")

</div>

That along with the article made it clear.Thanks.

---

<div class="post-metadata">

**Author:** ![darkknight001](https://discuss.codechef.com/user_avatar/discuss.codechef.com/darkknight001/32/3653_2.png) [@darkknight001](https://discuss.codechef.com/u/darkknight001)\
**Post date:** [April 15, 2020, 4:56pm UTC](https://discuss.codechef.com/t/strno-editorial/61191/19 "2020-04-15T16:56:18Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![believer](https://discuss.codechef.com/user_avatar/discuss.codechef.com/believer/32/493_2.png) [@believer](https://discuss.codechef.com/u/believer)\
**Post date:** [April 15, 2020, 4:58pm UTC](https://discuss.codechef.com/t/strno-editorial/61191/20 "2020-04-15T16:58:11Z")

</div>

this problem is all related to observation and nothing else.

---

<div class="post-metadata">

**Author:** ![believer](https://discuss.codechef.com/user_avatar/discuss.codechef.com/believer/32/493_2.png) [@believer](https://discuss.codechef.com/u/believer)\
**Post date:** [April 15, 2020, 5:01pm UTC](https://discuss.codechef.com/t/strno-editorial/61191/21 "2020-04-15T17:01:28Z")

</div>

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.

[Next page](https://discuss.codechef.com/t/strno-editorial/61191.md?page=2)