Fişierul intrare/ieşire:nkl.in, nkl.outSursăGrigore Moisil 2018, 10
AutorVlad MihalyAdăugată degrigore.moisilGrigore Moisil grigore.moisil
Timp execuţie pe test0.15 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Nkl

Se dă un număr natural nenul N. O secvenţă de K numere naturale nenule (a1,a2,…,ak) se numeşte L-perfectă dacă cel mai mic multiplu comun a oricăror L numere din secvenţa (a1,a2,…,ak) este N. Se cere să se determine numărul secvenţelor ordonate de K numere care sunt L-perfecte.

Date de intrare

Fişierul nkl.in conţine pe prima linie un număr natural N cu semnificaţia de mai sus, pe a doua linie un număr natural nenul Q, iar pe următoarele Q linii câte două numere K şi L separate printr-un spaţiu, cu semnificaţia din enunţ.

Date de ieşire

Fişierul nkl.out conţine Q linii, corespunzătoare celor Q perechi de numere K şi L. Pentru fiecare pereche se va afişa numărul secvenţelor ordonate de dimensiune K care sunt L-perfecte modulo 109 + 7.

Restricţii

  • 1 <= N <= 109.
  • 1 <= K, L, Q <= 1000.
  • L < K.
  • Pentru unele teste în valoare de 5 puncte K=3.
  • Pentru alt teste în valoare de 5 puncte L=2.
  • Problema va fi evaluată pe teste în valoare de 90 de puncte.
  • Exemplele vor reprezenta teste în valoare de 10 puncte "din oficiu".

Exemplu

nkl.innkl.out
6
1
3 2
16
6
1
5 3
256

Explicaţie

Pentru primul test, tripletele sunt: (1,6,6), (6,1,6), (6,6,1), (2,3,6), (3,2,6), (2,6,3), (6,2,3), (3,6,2), (6,3,2), (6,6,6), (2,6,6), (6,2,6), (6,6,2), (3,6,6), (6,3,6), (6,6,3)
Al doilea test este putin mai complicat.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?