Cần gợi ý hướng giải quyết bài tập đong nước

[MP_Shop]

[tntxtnt]

cứ múc đầy 1 bình rồi đổ hết vào bình còn lại, đầy bình còn lại thì đổ hết ra :V Cứ thế cho A, B rồi B, A, xem cái nào có số lần đổ ít hơn là đáp án

nhớ mang máng là vậy, đâu để thử coi
15 24 đong sao cho được 3
24/24 0/15
9/24 15/15
9/24 0/15
0/24 9/15
24/24 9/15
18/24 15/15
18/24 0/15
3/24 15/15
đó :V
tính ra đâu cần đổ 15/15, đã ra 3/24 là ra rồi

+15 -24 thì ta có 5x15 - 3x24 = 3 là 8 lần, 8 > 5 nên 5 là đáp án

bài toán quy về đi tìm Ax - By = C hoặc -Ax + By = C, sao cho tổng x + y nhỏ nhất :V đây gần giống với https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm toy tạm thời chưa nghĩ ra cách tìm nhanh :V

Ax - By = C thì y = (Ax - C)/B, y là số nguyên nên Ax - C chia hết cho B, vậy tìm x bé nhất sao cho Ax ≡ C (mod B) là được
https://math.stackexchange.com/questions/850903/finding-the-smallest-x-such-that-ax-equiv-b-mod-m ở đây bảo chia A B C cho gcd(A, B), nếu C ko chia hết cho gcd(A, B) thì vô nghiệm :V :V

-Ax + By = C thì x = (By - C)/A, hay tìm y bé nhất sao cho By ≡ C (mod A)

chia A, B, C cho gcd(A, B) rồi thì A’, B’ ng tố cùng nhau vậy có thể tính A’x’ ≡ 1 (mod B’) rồi nhân 2 vế cho C’ là ra A’x’C’ ≡ C’ (mod B’), hay x = x’C’ (mod B’)

để toy tính thử A=100 B=27 C=5
100x - 27y = 5
gcd(100, 27) = 1 vậy sau khi chia gcd(A, B) ta có 100 27 5
x’ = 100^-1 (mod 27) = 100^(18-1) (mod 27) = 10 (18 là phi(27), phi(n) là Euler’s totient function, công thức https://en.wikipedia.org/wiki/Euler’s_totient_function, công thức tính nghịch đảo A, B coprime ở đây: https://en.wikipedia.org/wiki/Modular_multiplicative_inverse#Using_Euler’s_theorem)
x = x’C’ (mod B’) = 10 * 5 (mod 27) = 50 % 27 = 23 ơ bự dữ vậy :V :V
x=23 vậy y = (100x23 - 5) / 27 = 85 x+y = 108

tính -100x + 27y = 5 vậy coi có ra đúng x+y=5 ko :V :V
y’ = 27^-1 (mod 100) = 27^(40-1) (mod 100) = 63
y = y’C’ mod 100 = 63x5 % 100 = 15
y = 15 thì x = (27x15 - 5) / 100 = 4
x+y=19 kì vậy :V :V

nhìn lộn đề C=8 mới đúng
x’=10 vậy x=80%27 = 26, y = 96
y’=63 vậy y=63x8%100 = 4, x = 1 ơ đúng này

với 1 giá trị x’ có thể có nhiều giá trị cho x, ko biết nhân lên vậy đúng ko để làm thêm ví dụ 1
15 24 3 chia gcd(15, 24) --> 5 8 1
x’ = 5^-1 mod 8 = 5 --> x = 5, y = 3
y’ = 8^-1 mod 5 = 2 --> y = 2, x = 3 ơ cũng đúng này

bài gì khó vậy phải viết gcd, rồi totient, rồi pow mod

à viết hàm tìm euler totient hơi khó, có thể xài thuật toán extended euclid gì ở trên đó để tìm cũng được

ơ đúng là chỉ cần chạy cái extended euclid là ra, gọi nó là egcd, trả về x’’, y’’ và gcd(a, b). Trực giác ban đầu thấy nó giống extended euclid đúng thật