Dans ce sujet, on s'intéresse à la somme des diviseurs stricts d'un nombre entier. Les diviseurs stricts de N sont tous les nombres K strictement inférieurs à N, tels que N soit multiple de K. Par exemple, la somme des diviseurs de 18 vaut
S(18) = 1 + 2 + 3 + 6 + 9 = 21
Les nombres parfaits sont les nombres N > 0 dont la somme des diviseurs S(N) vaut exactement N. Par exemple 6 et 28 sont de tels nombres parfaits :
S(6) = 1 + 2 + 3 = 6 S(28) = 1 + 2 + 4 + 7 + 14 = 28
Les nombres parfaits sont en fait très rares : il n'y en a que 5 plus petits que 100 millions ! On va ici s'intéresser aux nombres qui sont presque parfaits, c'est-à-dire dont la somme des diviseurs n'est pas loin de N. Plus précisément, étant donné deux entiers L et D, on souhaite connaître le nombre d'entiers strictement positifs et inférieurs ou égaux à L tels que l'écart entre le nombre et la somme de ses diviseurs soit inférieur ou égal à une constante D. Ecrit mathématiquement :
Le nombre de N vérifiant : 1 <= N <= L et valeur_absolue(S(N) - N) <= D
Par exemple, pour L=10, et D=1, on trouve 5 nombres vérifiant la propriété voulue : 1, 2, 4, 6, et 8, comme le montre le tableau suivant :
N S(N) |S(N)-N| -------------------- 1 0 1 2 1 1 3 1 2 4 3 1 5 1 4 6 6 0 7 1 6 8 7 1 9 4 5 10 8 2
De plus, dans 50% des tests, on a :
Vous devez écrire une ligne sur la sortie, contenant un entier K : le nombre d'entiers vérifiant la propriété voulue.
entrée :
10 1
sortie :
5