Johnny a été malade récemment et a manqué quelques cours. Il n'y a pas accordé beaucoup d'importance, à une exception près : la physique le passionne, alors il a emprunté les notes de cours de son ami. Ces notes lui ont appris qu'il avait manqué un cours sur le modèle de Bohr de l'atome d'hydrogène et… apparemment rien d'autre, car il a reconstitué à partir de ces notes le « modèle de Johnny-Bohr » suivant[^1]
L'électron qui gravite autour du noyau d'un atome d'hydrogène ne peut occuper que des orbites de rayons particuliers. À chacun de ces rayons correspondent une énergie et un moment cinétique particuliers de l'électron. Le moment cinétique est quantifié : il peut prendre toute valeur qui est un multiple entier strictement positif de la constante de Planck réduite $\hbar$ (également appelée constante de Dirac). Il est donc utile de numéroter les orbites par des entiers naturels, de sorte que l'orbite de numéro $n$ corresponde à un moment cinétique de $n\cdot\hbar$. Un électron peut passer d'une orbite $n_1$ à une orbite inférieure $n_2$ ($n_2<n_1$) ; la différence d'énergie est alors émise sous la forme d'un photon ayant une fréquence et une longueur d'onde appropriées. Le modèle de Johnny-Bohr ne prévoit pas la situation inverse, c'est-à-dire l'absorption d'un photon par l'atome et le passage de l'électron à une orbite supérieure. Le modèle précise exactement vers quelles orbites inférieures un électron peut sauter. Dans le cahier de son ami figure un multiensemble $B$ ayant la propriété suivante : un électron peut passer de l'orbite $a$ à l'orbite $\lfloor a/b\rfloor$ pour tout $b\in B$. L'électron peut ensuite sauter à nouveau depuis sa nouvelle orbite $a'$ selon cette même règle. En particulier, le modèle de Johnny-Bohr permet à un électron de passer à l'orbite (finale) de numéro $0$, c'est-à-dire de « tomber » sur le noyau. Tout comme pour le modèle de Bohr original, Johnny ne peut pas prouver que ce modèle décrit réellement le comportement de l'atome d'hydrogène, mais il peut vous assurer qu'il est compatible avec les données expérimentales (du moins celles des expériences de pensée de Johnny). Fier de sa compréhension approfondie du problème, Johnny a remarqué qu'il soulevait quelques questions intéressantes susceptibles de l'aider à mieux comprendre le comportement des atomes. La plus importante est la suivante : « Si un électron part de l'orbite de numéro $n$, combien d'orbites différentes (y compris $n$) peut-il atteindre en un nombre quelconque de sauts (éventuellement nul) ? »
Entrée
La première ligne du fichier d'entrée contient deux entiers $n$ et $m$ ($1\le n\le 10^{15}$, $1\le m\le 10$), désignant respectivement le numéro de l'orbite initiale de l'électron et la taille du multiensemble $B$. La deuxième (et dernière) ligne du fichier d'entrée contient une suite de $m$ entiers $b_i$, $1\le b_i\le 10^{15}$, séparés par des espaces simples ; ce sont les éléments du multiensemble $B$.
Sortie
Sur la première et unique ligne, affichez un seul entier : le nombre d'orbites différentes sur lesquelles l'électron peut se retrouver après un nombre quelconque de sauts en partant de l'orbite de numéro $n$.
Exemples
Entrée 1
20 2 2 3
Sortie 1
8
Remarque
En partant de l'orbite $n=20$ avec $B=\{2,3\}$, un électron peut atteindre (en 0 saut ou plus) chacune des huit orbites suivantes : $20,10,6,5,3,2,1,0$.
[^1]: Bien que ce modèle porte le nom de l'un des plus grands physiciens, il n'a pas grand-chose à voir avec la physique : l'ami de Johnny n'est pas particulièrement doué pour prendre des notes, et la fièvre de Johnny n'arrange rien !