Laiko ribojimas: 3s

Atminties ribojimas: 16MB

Jei norite pateikti savo sprendimą - prisijunkite.

Dalikliai

Matematikai mėgsta įvairiausias keistas skaičių savybes. Pavyzdžiui, jiems skaičius 945 yra įdomus, nes tai pirmasis nelyginis skaičius, kurio daliklių suma viršija patį skaičių.

Kad padėtumėte jiems ieškoti įdomių skaičių, parašykite programą, kuri nustatytų, kuris skaičius iš tam tikro intervalo turi daugiausiai daliklių. Deja, šie skaičiai bei intervalo ilgis yra gana dideli, tad paprastas algoritmas užtruks per daug laiko. Taigi pasirūpinkite, kad algoritmas būtų pakankamai gudrus susidoroti su didžiausiu galimu skaičių intervalu per vos kelias sekundes.

Pradiniai duomenys

Pirmoje eilutėje įrašytas intervalų skaičius N (iki 30). Sekančiose N eilučių pateikta po du skaičius L ir U, žyminčius uždarą intervalą [L, U]. Galioja apribojimai: 1\\leL\\leU\\le1~000~000~000 ir 0\\leU-L\\le10~000.

Rezultatai

Kiekvienam intervalui programa turi rasti skaičių P, kuris turi didžiausią skaičių daliklių (jei yra keli skaičiai, turintys didžiausią skaičių daliklių, P lygus mažiausiam iš jų), bei teigiamų P daliklių skaičių D (skaičiai 1 ir P taip pat yra P dalikliai). Programa turi išspausdinti P ir D, atskirtus vienu tarpo simboliu, atskiroje eilutėje kiekvienam testui.

Pavyzdžiai

Pradiniai duomenys Rezultatai 
3
1 10
1000 1000
999999900 1000000000
 
6 4
1000 16
999999924 192