Rezolvare PBinfo #3680

Pentru un număr natural nenul X, se numește divizor propriu al lui X, un divizor natural al lui X, diferit de 1 și X. De exemplu, pentru numărul 20 divizorii proprii sunt 2, 4, 5, 10, iar numărul 20 are 4 divizori proprii.

Cerința

1. Se dă un număr natural N. Determinați cel mai mic număr din intervalul închis [1,N] care are număr maxim de divizori proprii.
2. Se dau trei numere N, M și T. Determinați câte intervale de forma [a,b] au proprietatea că există exact M numere naturale care au T divizori proprii.

Date de intrare

Fișierul de intrare numere.in conține pe prima linie un număr natural P reprezentând cerința din problemă care trebuie rezolvată.

Dacă P = 1 atunci pe a doua linie se găsește un număr natural N, reprezentând extremitatea din dreapta a intervalului.

Dacă P = 2 atunci pe a doua linie se găsesc trei numere: un număr natural N, un număr natural M și un număr natural T cu semnificațiile din enunț.

Date de ieșire

Dacă P = 1 atunci fișierul de ieșire numere.out conține pe o singură linie numărul cel mai mic determinat care are număr maxim de divizori.

Dacă P = 2 atunci fișierul de ieșire numere.out conține pe o singură linie numărul de intervale determinate care au proprietatea cerută.

Restricții și precizări

• 1 ≤ N ≤ 100000
• 1 ≤ M ≤ 100000
• 1 ≤ T ≤ 100000
• 1 ≤ a ≤ b ≤ N
• Pentru rezolvarea corectă a cerinței 1 se acordă 40 de puncte, pentru rezolvarea corectă a cerinței 2 se acordă 60 de puncte.

Exemplul 1:

numere.in

1
20

numere.out

12

Explicație

12 are 4 divizori proprii și este cel mai mic număr cu 4 divizori proprii din [1,20].

Exemplul 2:

numere.in

2
10 3 2

numere.out

6

Explicație

[1,10], [2,10], [3,10], [4,10], [5,10], [6,10] sunt cele 6 intervale în care se găsesc exact 3 numere cu 2 divizori proprii(6, 8, 10 sunt numerele cu 3 divizori proprii).