Nombres quasi-parfaits

Remarque : aucune connaissance mathématique particulière n'est requise pour résoudre ce problème.

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

Limites de temps et de mémoire (Python)

  • Temps : 10 s sur une machine à 1 GHz.
  • Mémoire : 40 000 ko.

Contraintes

  • 2 <= L <= 1 000 000
  • 0 <= D <= 1 000 000

De plus, dans 50% des tests, on a :

  • 2 <= L <= 1 000

Entrée

  • La première ligne de l'entrée contient un entier : L
  • La deuxième ligne contient un entier : D

Sortie

Vous devez écrire une ligne sur la sortie, contenant un entier K : le nombre d'entiers vérifiant la propriété voulue.

Exemple

entrée :

10
1

sortie :

5

Source : http://www.france-ioi.org/ Créé par : Arthur Charguéraud, Mars 2005.