PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: kingmessi
Tester: pols_agyi_pols
Editorialist: iceknight1093
DIFFICULTY:
Medium
PREREQUISITES:
None
PROBLEM:
You’re given the integers X and M.
You can do the following:
- Choose a positive integer K such that 1 \le K \le M.
- Change X to either X+K or X-K.
- This has a cost of \varphi(K), where \varphi denotes the Euler totient function.
Find the minimum cost of making X equal to D.
EXPLANATION:
To begin, we have
Let’s use this to analyze the types of moves we make.
First, one simple observation is that it’s always optimal to choose square-free numbers as K.
That is, there must not exist any prime p such that p^2\mid K.
This is simply because, if p^2 \mid K, then \varphi(K) = p\cdot \varphi(\frac{K}{p}), so rather than use K for a cost of \varphi(K), we can use \frac{K}{p}, p times and obtain the same value with the same cost.
Repeating this argument eventually leaves us with a square-free number (which will be exactly the product of all distinct primes dividing the initial K).
Now, we have only square-free numbers, meaning they’re products of distinct primes.
Consider the sequence of all prime numbers in ascending order, i.e [2, 3, 5, 7, 11, \ldots]
Let p_i denote the i-th prime in this sequence.
Let P_i = p_1\cdot p_2\cdot\ldots\cdot p_i denote the product of the first i primes.
(This is also called the i-th primorial, as in factorial but with primes.)
Then, it can be proved that even among square-free numbers, it’s always optimal to use primorials.
Proof
Let K be a square-free number that’s not a primorial.
For now, consider the special case where K = p_1p_2\ldots p_i \cdot q where q \gt p_{i+1}.
Observe that \varphi(K) = (p_1-1)\cdot (p_2-1) \cdot \ldots \cdot (p_i-1) \cdot (q-1) = \varphi(P_i) \cdot (q-1).
Now, instead of using K, suppose we use one copy of P_{i+1} and (q - p_{i+1}) copies of P_i instead.
The total distance covered equals p_{i+1}\cdot P_i + (q - p_{i+1}) \cdot P_i = q\cdot P_i = K, so that stays the same.
The cost of this is (p_{i+1}-1)\cdot \varphi(P_i) + (q - p_{i+1}) \cdot \varphi(P_i) = (q-1)\cdot \varphi(P_i), which is also the same.So, we’re able to replace K by several primorial moves without increasing the cost.
Thus, there exists a sequence of optimal moves only using primorials, as claimed.
Note that since M \le 10^{15}, the number of primorials available to us is quite small: in particular, P_{14} \gt 10^{15} so we only need to care about the first 13 or so of them.
Let r denote the largest index such that P_r \le M, so we only have P_0, P_1, P_2, \ldots, P_r available to use.
(Here, P_0 = 1.)
We want to assign coefficients c_i to these in such a way that
where the cost of such an assignment is \sum_{i=0}^r |c_i|\cdot \varphi(P_i).
Let’s try to decide these values from left to right.
Suppose we’ve decided the values of c_0, c_1, \ldots, c_i, and the current value is S.
Then, observe that because the primorials divide each other, no matter how higher coefficients are decided, S will remain the same modulo P_{i+1}.
So, after deciding all of c_0, \ldots, c_i, we must certainly have S \equiv N \pmod P_{i+1}.
Now, it can be seen that if r = N \bmod P_{i+1} is the remainder, it’s in fact optimal to have S equal either r itself, or r - P_{i+1} (since negative coefficients are allowed).
It’s never optimal for the value to be outside (-P_{i+1}, P_{i+1}) though, since for such ‘large’ values it’s better to use copies of P_{i+1} to reach them instead; because we have \frac{\varphi(P_i)}{P_i} \gt \frac{\varphi(P_{i+1})}{P_{i+1}} (the higher primorials have better cost-per-unit).
More formally, the above cost-per-unit argument proves that it’s optimal for c_i \in (-p_{i+1}, p_{i+1}) to hold, and this combined with the primorials dividing each other shows that any optimal combination of the first i primorials cannot exceed the (i+1)-th in value.
The observation about S = r or S = r - P_{i+1} gives us a dynamic programming solution.
Define dp_{i, j} to be the minimum cost to use P_0, P_1, \ldots, P_i to form:
- N \bmod P_{i+1}, if j = 0
- (N \bmod P_{i+1}) - P_{i+1}, if j = 1
These are trivial to compute now, since dp_{i, j} can be computed in \mathcal{O}(1) from dp_{i-1, 0} and dp_{i-1, 1}.
If r is the index of the largest allowed primorial, the answer is then trivially computed from knowing dp_{r, 0} and dp_{r, 1}.
The complexity of this is about \mathcal{O}(\log M).
TIME COMPLEXITY:
\mathcal{O}(\log M) per testcase.
CODE:
Editorialist's code (PyPy3)
def isprime(n):
i = 2
while i*i <= n:
if n%i == 0: return False
i += 1
return n > 1
prod = [1]
cost = [1]
for n in range(2, 100):
if isprime(n):
prod.append(prod[-1] * n)
cost.append(cost[-1] * (n-1))
if prod[-1] > 10**18: break
for _ in range(int(input())):
m, d = map(int, input().split())
if m == 1:
print(d)
continue
dp = [ [0, 0] for _ in range(15) ]
if d%2 == 1:
dp[0][0] = 1
dp[0][1] = 1
else:
dp[0][1] = 2
for i in range(1, 15):
if prod[i] <= m:
cvals = [d % prod[i+1], d % prod[i+1] - prod[i+1]]
pvals = [d % prod[i], d % prod[i] - prod[i]]
dp[i][0] = dp[i][1] = d+1
for j in range(2):
for k in range(2):
dif = abs(cvals[j] - pvals[k])
ops = dif//prod[i]
dp[i][j] = min(dp[i][j], dp[i-1][k] + ops * cost[i])
else:
pvals = [d % prod[i], d % prod[i] - prod[i]]
ans = d+1
for j in range(2):
ans = min(ans, dp[i-1][j] + abs(d - pvals[j]) * cost[i-1] // prod[i-1])
print(ans)
break