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.