(Tachado 44 sigue siendo 44.) ¡ Gracias a Fireflame241 por guardar un byte!
P=input();i=P/3
while i*10%P-1:i-=1
print i
Pruébalo en línea!
Hay exactamente un número entre 0y P-1que es un inverso de 10. Pero si ese inverso ues mayor que P/2, entonces (u-P)también es inverso y tiene un valor absoluto menor que u. Resulta que realmente estamos buscando el número único xentre -P/2yP/2 que es un inverso de 10.
El código anterior hace exactamente eso, comenzando en (el piso de) P/2y bajando hasta alcanzar un inverso. Esto debe suceder para un número mayor que -P/2mientras Psea un primo mayor que 10. Más precisamente, terminará si y solo si Pes coprime para10 .
Editar: en realidad resulta que xestá garantizado entre -P/3y P/3, por lo que la versión actual comienza en P/3y baja desde allí. Ver la sección etiquetada Mejorado vinculado para obtener una explicación de esto.
Explicación matemática
No fue inmediatamente obvio para mí por qué funcionó la prueba de divisibilidad. Aquí hay una explicación, en caso de que alguien más se preguntara.
Sea Pun primo, mayor que 10, cuyo último dígito es b. Así
P = 10a + b
donde a > 0y 0 <= b < 10. De hecho bes o bien 1, 3, 7, o 9, a causa de una mayor prime10 final necesidad en uno de estos dígitos.
Ahora supongamos bx + a = 0 (mod P). Luego
a = -bx (mod P)
10a + b = 10(-bx) + b (mod P)
0 = 10(-bx) + b (mod P)
0 = b(1 - 10x) (mod P)
Como Pes primo, los enteros mod Pson un dominio integral . Entonces b = 0 (mod P), o 1 - 10x = 0 (mod P).
Sabemos 0 <= b < 10 < P, por lo que si b = 0 (mod P)a continuación b = 0. Pero dijimos bestá bien 1, 3, 7, o 9, por lo que esto es imposible. Por 1 - 10x = 0 (mod P)lo tanto , entonces 10x = 1 (mod P). En otras palabras, xes el inverso de 10, módulo P.
Ahora suponga que Nes un entero no negativo cuyo último dígito es d, por N = 10c + d. lo que tenemos una cadena de declaraciones equivalentes:
10c + d = 0 (mod P)
<==> 10xc + dx = 0 (mod P)
<==> c + dx = 0 (mod P)
QED
¿Utilidad?
También me preguntaba si la prueba de divisibilidad (dada N = 10c + d, reemplazada Npor dx + c) sería realmente productiva en la práctica. O al menos, ¿se reemplaza confiablemente Npor un número menor que N(en valor absoluto)?
Supongamos N = 10c + d, donde c >= 0y 0 <= d < 10. Por lo tanto 10c = N - d <= N. Por la desigualdad del triángulo,
|c + dx| <= |c| + |dx| = c + d|x| <= N/10 + d|x|
< N/10 + 10|x| <= N/10 + 10P/2 = N/10 + 5P
Entonces si 5P <= 9N/10, entonces |c + dx| < N.
En particular, si N >= 6P, entonces |c + dx| < N. Por lo tanto, dado Pque comenzamos calculando 2P, 3P, ..., 6P, junto con x. Entonces dado N, corremos el test de la divisibilidad en repetidas ocasiones hasta llegar a un número menor o igual a 6P, y comprobar si el resultado es cualquiera de los números 0, P, 2P, ..., 6P.
(Por supuesto, cada vez que alcanzamos un número negativo, lo reemplazamos por su valor absoluto, lo cual está bien ya que qes divisible por Psi y solo si lo (-q)es).
Límite mejorado
Me di cuenta de que |x|/Pnunca parecía estar cerca 1/2. De hecho, parecía que siempre era menor que 1/3... o, al examinarlo más de cerca, siempre estaba muy cerca de uno 1/10u otro 3/10. El más grande que haya tenido parece ser 4/13(lo que sucede cuando P=13y x=4). ¿Por qué sería esto?
Deje user un número entero y suponga que 10u = kP + 1para algún número entero k, también lo ues un 10módulo inverso P. Entonces también sabemos que kes relativamente primo 10, ya que k(-P)es equivalente al 1módulo 10.
Ahora, sabemos que todas las inversas del 10módulo Pdifieren en múltiplos de P, por lo que podemos tomar el número entero uy sumar o restar múltiplos Pa voluntad, y el resultado siempre será un inverso del 10módulo P. Supongamos que elegimos restar Pde u: obtenemos
10(u - P) = 10u - 10P = kP + 1 - 10P
10(u - P) = (k - 10)P + 1
En otras palabras, la disminución (respectivamente, aumentando) upor Pcorresponde a la disminución (en aumento) kpor 10. Queremos añadir / restar múltiplos de Ppartir uhasta que el lado izquierdo se reduce al mínimo en valor absoluto; pero el lado izquierdo se minimiza exactamente cuando se minimiza el lado derecho, y así queremos añadir / restar 10dek hasta que el lado derecho se reduce al mínimo en valor absoluto.
Pero sabemos que esto sucederá cuando kestá entre -5y 5, y por lo tanto (ya que kes relativamente primos a 10) este medio kes o bien -3, -1, 1, o 3. (Este es el contenido del comentario de @ Neil bajo el OP. ¡ Gracias, Neil! )
Así, cuando |u|se reduce al mínimo (es decir, u=x), tendremos x/P = u/P = k/10 + 1/(10P), donde kes o bien -3, -1, 1, o 3. Por lo tanto |x|/P <= 3/10 + 1/(10P). De manera equivalente, |x| <= (3P + 1)/10.
Además, esta desigualdad es estricta en P=11, porque en P=11tenemos x=-1y k=-1. El más pequeño Ppara el que se cumple la igualdad es P=13(dónde x=4y k=3).
Por lo tanto, el más grande que |x|/Pse obtiene es 3/10 + 1/(10*13), porque P=13es el primer primo para el que tenemos k=3, y entre aquellos con k=3, el 1/(10P)término es más grande cuando Pes más pequeño (es decir, en P=13). Por lo tanto, para todos P, también tenemos |x|/P <= 3/10 + 1/130 = 4/13 < 1/3. Esto explica por qué en el código anterior podemos inicializar en i = P/3lugar de tener que comenzar enP/2 .
Además, los límites en la utilidad sección de anterior ahora se pueden mejorar.
Lema : Dejar N = 10c + ddónde c > 0y 0 <= d <= 9. Luegoc + d|x| < N/10 + 9(3P + 1)/10 . (Tenga en cuenta la estricta desigualdad).
Prueba de Lemma: por casos. Caso I: d = 0entonces N = 10c. Luegoc + d|x| = c = N/10 < N/10 + 9(3P + 1)/10 .
Caso II: 0 < d <= 9. Entonces 10c = N - d < N, entonces c < N/10. Por lo tantoc + d|x| < N/10 + d|x| <= N/10 + 9|x| <= N/10 + 9(3P + 1)/10 . QED
Por lo tanto, si N > 3P(y N = 10c + dcomo antes), entonces
3P + 1 <= N
9(3P + 1)/10 <= 9N/10
N/10 + 9(3P + 1)/10 <= N
c + d|x| < N/10 + 9(3P + 1)/10 <= N
Entonces, si N > 3Pentonces c + d|x| < N.
Por lo tanto, solo tenemos que encontrar P, 2Py 3P, junto con x. Dado N > 0, mientras N > 3P, reemplazamos Npor |c + dx|, lo que disminuye N. Finalmente lo conseguiremos N <= 3P; en ese punto nos detenemos y comprobar si Nes igual a cualquiera de los números 0, P, 2P, o 3P.
No podemos hacerlo mejor que 3Pen general. Por ejemplo, supongamos P = 13y N = 39, entonces x = 4. Luego reemplazando Npor dx + c = 9(4) + 3hojas Nsin cambios.
xvalor absoluto más pequeño donde10*x-1sea divisible por la entrada.(3 / (n % 5 * 2 - 5) * n + 1) / 10y(n % 5 * 2 - 5^2) * n / 10 + 1puede encontrar un valor absoluto mínimo para algo como esto? Mi primera intuición habría sido calcular el mínimo común múltiplo utilizando el máximo común divisor calculado con el algoritmo de Euclides.x, agregarlo y aún así obtener un número divisible porn. Si luego multiplicamos el nuevo número por 10 y restamos el número original, sigue siendo divisible porn. El comentario de xnor se desprende de un poco de álgebra. El siguiente paso es reorganizar la fórmula de modo que déxen términos den: x =(k*n+1)/10. Queremos que el más pequeño absolutaxpor lo que, por lo tanto queremos que el más pequeño absolutak, y esto debe ser lo que uno de-3,-1,1o3(dependiendo den'último dígito s) que hace que la división exacta.