magnify

Savarankiški skaičiai

Pradinių duomenų failas:
skaiciai.in  
Rezultatų failas:
skaiciai.out  
Laiko apribojimas:
1 s.  
Atminties apribojimas:
16 Mb.  

Užduotis

1949 m. indų matematikas D.R. Kaprekar apibrėžė klasę skaičių, vadinamų savarankiškais skaičiais.

Bet kokiam teigiamam skaičiui n apibrėžkime d(n) kaip skaičiaus n ir jo skaitmenų sumą. (Raidė d naudojama dėl Kaprekar įvesto termino digitadition (skaitmenų sudėtis).) Pavyzdžiui, d(75) = 75 + 7 + 5 = 87. Pradėdami nuo bet kokio teigiamo skaičiaus n, galime sukonstruoti begalinę didėjančią teigiamų skaičių seką n, d(n), d(d(n)), d(d(d(n))), … Pavyzdžiui, jei pradėtume nuo 33, sekantis sekos narys būtų 33 + 3 + 3 = 39, dar sekantis – 39 + 3 + 9 = 51, dar sekantis – 51 + 5 + 1 = 57, ir taip toliau. Gautume seką:

33, 39, 51, 57, 69, 84, 96, 111, 114, 120, 123, 129, 141, ...

Skaičius n yra vadinamas skaičiaus d(n) generatoriumi. Iš mūsų nagrinėtos sekos matyti, kad 33 yra skaičiaus 39 generatorius, 39 yra 51 generatorius, ir taip toliau. Kai kurie skaičiai turi daugiau negu vieną generatorių, pavyzdžiui, 101 turi du generatorius: 91 and 100. Skaičiai, neturintys generatorių, vadinami savarankiškais skaičiais. Yra trylika savarankištų skaičių, mažesnių negu 100: 1, 3, 5, 7, 9, 20, 31, 42, 53, 64, 75, 86, ir 97.

Parašykite programą, kuri išspausdintų visus savarankiškus skaičius, priklausančius duotam intervalui.

Pradiniai duomenys

Pirmoje ir vienintelėje pradinių duomenų failo eilutėje įrašyti du sveikieji teigiami skaičiai a ir b. (1 <= a < b <= 1000000).

Rezultatai

Visus savarankiškus skaičius, priklausančius intervalui [a, b] turi įrašyti į rezultatų failą, didėjančia tvarka, po vieną eilutėje.

Pavyzdžiai

Pradiniai duomenys Rezultatai
1 100
1
3
5
7
9
20
31
42
53
64
75
86
97
© Bronė Narkevičienė