PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: iceknight1093
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Simple
PREREQUISITES:
Factorization
PROBLEM:
You have integers X, Y, Z, C. You can do the following:
- Increase or decrease Z by 1, as long as it remains \geq 1.
This has a cost of 1. - Set X \gets \gcd(X, Z) and Y\gets \text{lcm}(Y, Z).
This has a cost of C. - Set Y \gets \gcd(Y, Z) and X\gets \text{lcm}(X, Z).
This also has a cost of C.
Find the minimum cost of making X and Y equal.
EXPLANATION:
If X = Y initially the cost is obviously 0, so we only consider X \neq Y.
The only way to change X and Y is using the gcd/lcm operations, so obviously our last operation must be one of them.
Let a “type 1” operation mean X \to \gcd(X, Z) and Y \to \text{lcm}(Y, Z), and a “type 2” operation be the opposite.
Notice that if we perform a type 1 operation,
- \gcd(X, Z) will be a factor of Z, meaning it will be \leq Z.
- \text{lcm}(Y, Z) will be a multiple of Z, meaning it will be \geq Z.
- So, the only way these can be equal after the operation, is if they’re both equal to Z itself, i.e. \gcd(X, Z) = Z = \text{lcm}(Y, Z).
Now, \gcd(X, Z) = Z will be true if and only if X is a multiple of Z, and \text{lcm}(Y, Z) = Z will be true if and only if Y is a factor of Z.
Note that if both conditions are true, then Y will also be a factor of X; and when Y is a factor of X, any value of Z such that it’s a multiple of Y and a factor of X will make X = Y.
The above analysis only told us about the very last move. What about before that?
Well, if X is initially a multiple of Y, we can just try all candidates for the operation to perform.
This can be done by just checking all factors of X (in \mathcal{O}(\sqrt X) time), and for each factor d which is a multiple of Y, we’ll need |d-Z| + C moves.
The first term comes from needing to increment/decrement Z till it reaches d, while the second term comes from performing the type 1 operation.
If Y is a multiple of X instead, we can do the same thing but with factors of Y instead.
However, observe that this only takes care of situations where we perform only one type 1/type 2 operation: it doesn’t take care of any situations where we might need to perform more.
The next natural question is: how many type 1/2 operations are needed at all?
If you analyze a bit, you may notice that it’s always possible to make X and Y equal by performing a type 1 operation followed by a type 2 operation (with the same value of Z).
This is because, after the type 1 operation X will be a factor of Z and Y will be a multiple of Z; so X will be a factor of Y.
Then performing the type 2 operation with this Z will make both equal to Z.
So, performing two type 1/2 operations will always allow us to make X and Y equal.
This is completely independent of the value of Z, so we don’t even need to spend any moves on changing the value of Z: the cost is just 2C.
This takes care of us ever needing more than one change operation, and is obviously optimal for that case - so the only thing that needs consideration is whether one change operation will suffice (which we’ve already seen how to check).
Thus, we have a fairly simple solution:
- If X = Y, the answer is 0.
- Otherwise, initialize the answer to 2C.
- Then, if X is a divisor of Y, update the answer with |d-Z| + C for each divisor d of Y that’s also a multiple of X.
If Y is a divisor of X, do the same thing but with X and Y swapped.
TIME COMPLEXITY:
\mathcal{O}(\sqrt{\max(X, Y)}) per testcase.
CODE:
Editorialist's code (PyPy3)
for _ in range(int(input())):
x, y, z, c = map(int, input().split())
# two ops
ans = 2 * c
# one op
if x > y: x, y = y, x
if y%x == 0:
i = 1
while i*i <= y:
if y%i == 0:
if i%x == 0: ans = min(ans, c + abs(i - z))
if (y//i)%x == 0: ans = min(ans, c + abs(y//i - z))
i += 1
# no op
if x == y: ans = 0
print(ans)