PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: suman_18733097
Tester: mexomerf
Editorialist: iceknight1093
DIFFICULTY:
simple
PREREQUISITES:
Factorization
PROBLEM:
Chef has a health of H, which he can multiply by some number between 1 and K.
When fighting a monster, his health decreases to its largest factor other than itself, till it reaches 1.
Find the maximum number of monsters Chef can defeat if the multiplier is chosen optimally.
EXPLANATION:
The largest factor of H that isn’t H itself, is \frac{H}{p} where p is the smallest prime factor of H.
Proof
If x is a factor of H, that means there exists some other integer y such that x\cdot y = H.
So, any factor of H is of the form \frac{H}{y} for some integer y.
However, for \frac{H}{y} to be an integer, y must also be a factor of H.Since we’re looking for the largest factor of H, we want \frac{H}{y} to be as large as possible; which means y should be as small as possible, since \frac{1}{y_1} \gt \frac{1}{y_2} when y_1 \lt y_2.
The absolute smallest y we can choose is y = 1, of course - but this would just give us H as the factor, which we don’t want.
So, we choose the smallest y \gt 1 that we can, i.e, the smallest possible non-1 factor of H.This y has to be a prime number: if it isn’t, then it’ll have some other prime factor p that’s strictly smaller than it, and since p divides y and y divides H, p also divides H - contradicting y being the smallest non-1 factor of H.
So, the largest factor of H that’s less than it is \frac{H}{y} where y is the smallest prime factor of H, as claimed.
In other words, each time Chef defeats a monster, H loses exactly one of its prime factors.
So, the total number of monsters Chef can defeat is its simply the number of prime factors of H (repetitions included).
For example, if H = 120 = 2^3 \cdot 3^1 \cdot 5^1, the number of monsters that can be defeated is 3+1+1 = 5.
Now that we know this, let’s solve the actual problem.
Let p(x) denote the number of prime factors of x.
Then, note that for any positive integers x and y, p(x \cdot y) = p(x) + p(y).
So, no matter what multiplier x is chosen in [1, K], we’ll have p(H\cdot x) = p(H) + p(x).
Our goal is to maximize p(H\cdot x), which means we simply have to choose the maximum possible p(x).
With our goal being purely to maximize the number of prime factors, it’s enough to look at powers of 2.
This is because, if we choose a number with a prime factor larger than 2, we could’ve instead replaced that prime factor with 2 to get a smaller number (so it remains \leq K) with the same number of primes.
So, we simply choose the multiplier to be the largest power of 2 that doesn’t exceed K.
If this is 2^x, we have p(2^x) = x, so add x to p(H) to obtain the final answer.
To compute p(H), we want to know the number of prime factors of H.
This can be found by simply factorizing H naively in \mathcal{O}(\sqrt H) time.
TIME COMPLEXITY:
\mathcal{O}(\sqrt H + \log K) per testcase.
CODE:
Author's code (C++)
#include <iostream>
#include <cmath>
using namespace std;
void solve() {
int N = 0; long K = 0;
cin >> N >> K;
int ans = 0;
for (int i = 2; i <= sqrt(N); i++) {
for (; N % i == 0; N /= i, ans++);
}
if (N > 1) {
ans++;
}
for (; K > 1; K /= 2, ans++);
cout << ans << '\n';
}
int main() {
int t = 0;
cin >> t;
while (t--) {
solve();
}
return 0;
}
Tester's code (C++)
#include <bits/stdc++.h>
using namespace std;
#define N 1000001
#define int long long
int32_t main() {
int dp[N] = {};
for(int i = 2; i < N; i++){
if(dp[i]){
continue;
}
int x = i;
while(x < N){
int xx = x;
while(xx % i == 0){
dp[x]++;
xx /= i;
}
x += i;
}
}
int t;
cin>>t;
while(t--){
int h, k;
cin>>h>>k;
int temp = 1;
int ans = dp[h];
while(2 * temp <= k){
temp *= 2;
ans++;
}
cout<<ans<<"\n";
}
}
Editorialist's code (PyPy3)
for _ in range(int(input())):
h, k = map(int, input().split())
ct = 0
for i in range(2, h+1):
while h%i == 0:
h //= i
ct += 1
if i*i > h: break
ct += h > 1
ct += len(bin(k)) - 3
print(ct)