Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | nkl.in, nkl.out | Sursă | Grigore Moisil 2018, 10 |
| Autor | Vlad Mihaly | Adăugată de |  Grigore Moisil •grigore.moisil |
| Timp execuţie pe test | 0.15 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/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 1000000007.
Restricţii
- 1 <= N <= 1000000000
- 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
- Se vor acorda 10 puncte din oficiu
Exemplu
| nkl.in | nkl.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.
