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.