Armée

Jack, l'oncle de Stofl la souris, a été nominé comme commandant-en-chef de l'armée de Fromageland. Jack aimerait connaître le plus rapidement possible l'effectif total de son armée. Jusqu'à maintenant, il ne sait qu'une chose: le nombre total de soldats est compris entre $A$ et $B$.

Pour déterminer le nombre exact, il demande à ses soldats de former des rangs contenant chacun $x$ soldats. Jack regarde ensuite la dernière rangée et compte les soldats dans cette rangée (un nombre entre $0$ et $x-1$).

Comme chaque soldat doit compter jusqu'à $x$ pour savoir s'il peut aller dans une certaine rangée ou non, la formation de rangées de longueur $x$ prend un temps $x$.

Si le nombre de soldats de Fromageland n'est pas clair après la formation des rangs, Jack choisit un nouveau nombre $y$ et les soldats doivent former des rangs de $y$ soldats. Ils forment des rangs de $y$ soldats, ce qui prend un temps $y$. Jack répète cette étape jusqu'à ce qu'il soit sûr de connaître le nombre exact de soldats sous ses ordres.

Aide Jack à compter ses soldats le plus rapidement possible.

Tâche

Connaissant les entiers $A$ et $B$, détermine les nombres {$x,y,z,…$} que Jack doit appeler de façon à ce qu'il connaisse le nombre exact de soldats sous ses ordres et que la somme des nombres choisis soit minimale.

Entrée

L'entrée consiste en une ligne qui contient deux entiers $A$ et $B$, qui décrivent le domaine possible pour la taille réelle de l'armée.

Sortie

La sortie doit contenir deux lignes. La première doit contenir un entier $N$, le nombre de nombres choisis par Jack.

La deuxième ligne doit contenir ces $N$ nombres, séparés par des espaces.

InputOutput

A B

N
$a_1$ $a_2$ ... $a_N$

Exemple

InputOutput

1 8

2
2 5

Bien sûr, Jack connaîtrait le nombre de soldats s'il appelait 8. Mais avec la combination de 2 et 5, chaque quantité entre 1 et 8 peut être distinguée de toutes les autres et ça ne prend que 2+5=7 à la place de 8 unités de temps.

Astuce

En faisant des recherches pour son oncle Jack, Stofl a découvert qu'un officier chinois avait déjà utilisé une méthode similaire pour compter son armée. Sa méthode est connue comme 'Théorème des restes chinois'.

Voici une courte description de cette méthode :

Tout comme Jack, l'officier chinois appelle un nombre pour que son armée s'aligne en rangs de longueur correspondante. Il n'appelle que des nombres premiers entre eux et note le nombre de soldats dans la dernière rangée.

Exemple:

On veut déterminer le nombre de soldats x comme suit:

rangs de 3: il reste 1 soldat dans la dernière rangée

rangs de 4: il reste 3 soldat dans la dernière rangée

rangs de 5: il reste 2 soldat dans la dernière rangée }

Nous pouvons aussi dire que le nombre de soldats $x$ aura un reste de 1 si on le divise par 3, ou que $x$ modulo 3 est égal à 1. On écrit cela «$x = 1$ mod $3$» et une telle équation s'appelle une congruence.

$3$, $4$ et $5$ sont premiers entre eux. Nous définissons maintenant les tailles des rangs $m_1=3, m_2=4, m_3=5$ et les restes $r_1=1, r_2=3, r_3=2$.

Par ailleurs, nous choisissons $m=$ lcm$(m_1,…,m_n)=\Pi_{i=1}^{n}{m_i}=m_1*m_2*m_3=3*4*5=60$, où lcm dénote le dernier multiple commun.

Le théorème des restes chinois dit que chaque nombre entre $0$ et $m-1$ peut être décrit par une unique combinaison de restes $r_1, …, r_n$.

Nous allons maintenant examiner comment trouver $x$ en se basant sur les $m_i$ et les $r_i$. Dans ce but, nous calculons $M_i = m/m_i$, donc pour notre exemple : $M_1=20, M_2=15, M_3=12$.

Ensuite, ce sera la partie la plus difficile mathématiquement: nous allons déterminer l'inverse multiplicatif de $M_i$ modulo $m_i$. Cela veut dire que nous allons chercher des nombres $y_i$ tels que $y_i*M_i = 1$ mod $m_i$.

Il existe un algorithme appelé 'algorithme d'Euclide étendu' qui calcule ces inverses, mais il n'a pas besoin d'être expliqué en détail ici. Pour notre exemple, nous pouvons simplement trouver les inverses en essayant :

$y_1 = 2$, comme $2*20 = 40$, qui, en modulo 3, est égal à $40 - 13*3 = 1$.

Similairement, $y_2 = 3$, car $3*15$ modulo 4 est égal à $45 - 11*4 = 1$

et $y_3= 3$, comme $3*12$ modulo 5 est égal à $36 - 7*5 = 1$.

Nous avons maintenant tous les ingrédients pour calculer $x$. Nous obtenons:

$x = \sum_{i=1}^{n}(r_i*y_i*M_i)$ mod $m$.

Dans notre exemple, nous trouvons donc :

$x=(1*2*20 + 3*3*15 + 2*3*12)$ mod 60 = 247 mod 60 = 7.

Dans l'exemple, l'officier chinois a donc 7 soldats sous ses ordres.

Pour résumer, nous pouvons, après avoir appeler une suite de nombres premiers entre eux, différencier tous les nombres entre $0$ et (le plus petit multiple commun de ces nombres - 1).

Plus de détails sur le théorème des restes chinois et l'algorithme d'Euclide étendu peuvent être trouvés ici:

Le théorème des restes chinois sur Wikipedia:

http://fr.wikipedia.org/wiki/Théorème_des_restes_chinois

Informatikdepartement der FH Flensburg über den chinesischen Restsatz (en German):

http://www.inf.fh-flensburg.de/lang/krypto/algo/chinese-remainder.htm

L'algorithme d'Euclide étendu Wikipedia:

http://fr.wikipedia.org/wiki/Algorithme_d'Euclide_étendu

Envoi