Red de conocimiento informático - Conocimiento informático - Programación del teorema de Sun Tzu

Programación del teorema de Sun Tzu

Leí el libro durante mucho tiempo antes de responder esta pregunta. Había un algoritmo en la antigua China llamado "Da Luo Find One Technique". Una explicación sencilla es: encontrar un número n tal que se divida por A1, r2 dividido por A2, r3 dividido por A3, r4... dividido por A4. La expresión algebraica es: n = a 1q 1+r 1 = a2q 2+R2 = a3q 3+R3 = a4q 4+R4 =... Entonces la "gran derivación" requiere que primero encontremos un número M1 y lo dividamos por A1. Encuentra otro número M2, que sigue siendo 1 cuando se divide por A2, y es divisible por B2 = a 1×a3×A4 Encuentra un número M3, que sigue siendo 1 cuando se divide por A3, y es divisible por B3 = a 1×; a2×A4 ; Encuentra otro número M4, que sigue siendo 1 cuando se divide por A4, y es divisible por B4 = a 1×a2×A3 y así sucesivamente. La serie anterior del proceso de "encontrar uno" equivale a resolver una serie de ecuaciones indefinidas: BiX+AiY=1, (i=1, 2, 3, 4... Luego, cuando A1, A2, A3, A4). son primos relativos Cuando , la solución Xi (i = 1, 2, 3, 4 ...) se puede obtener mediante división de fases. Entonces, si Mi=BiXi, entonces m 1r 1+m2r 2+m3r 3+M4 r4 es un número dividido por A1, r2 dividido por A2, r3 dividido por A3, R4 dividido por A4, más o menos a1× A2.

Ahora usa las propiedades anteriores para resolver este problema:

Encuentra el número que es divisible por 11 y divisible por 13× 17× 19 = 4199. División euclidiana: 4199-11×381 = 8; 11-8=3; 8-3×2=2; entonces 1 = 3-2 = 3-(8-3×2)= 3 × 3-8 =(11-8)×3-8 = 11×3-8×4 = 65448. 01×1527, entonces obtenemos m 1 =-4199×4 =-16796. De la misma manera, también podemos obtener M2=-10659, M3=-16302, M4=-2431. En el problema, r1=5, r2=6, r3=8, r4=9, entonces m 1r 1+m2r 2+m3r 3+M4 R4 =-300229, y tenga en cuenta que es 11×10 dividido por 13. , 8 Dividido por 17, el número natural más pequeño que divide 9 entre 19 es -300229+46189×7=23094.

Si el cartel no entiende qué es la división, busque información usted mismo. Muy comprensible.

Finalmente terminé de escribirlo, y la persona que había estado tocando durante mucho tiempo dijo, ¡jaja, terminemos!