Getting (M + Ax) - (N + By) so nahe wie möglich

Question

Für vier vordefinierte Variablen N, M, A und B möchte ich irgendwie x und y so erhalten, dass der Unterschied zwischen den beiden ist minimiert, wie würden wir das erreichen?

Hinweis: A und B sind eindeutig!

Edit: Beispiel um dies deutlicher,

Say N = 4, M = 5. Dann A = 2 und B = 4, die offensichtliche Lösung ist, x gleich 4 ist, und y = 1, was ergibt 9 und 10. Ein Unterschied von 1. Aber das ist trivial, und mit größeren Zahlen kann ich nicht schnelle Ergebnisse mit meinem Gehirn allein, ich war neugierig auf eine allgemeinere Lösung.

Answer 1

Ax - By kann ein beliebiges ganzzahliges Vielfaches von gcd(A, B) und keine anderen Zahlen darstellen. Das nächste ganzzahlige Vielfache von gcd(A, B) bis M - N ist entweder floor((M - N)/gcd(A, B)) * gcd(A, B) oder ceil((M - N)/gcd(A, B)) * gcd(A, B). Das ist entweder M-N oder bis zum nächsten Vielfachen von gcd(A, B).

Ax - By = gcd(A, B) Lösen Sie das Extended Euclidean Algorithm mit und multiplizieren dann durch beide von x und y entweder durch floor((M - N)/gcd(A, B)) oder ceil((M - N)/gcd(A, B)) je nachdem, welche der beiden Ausdrücke im ersten Absatz am nächsten M - N.