Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | sirgcdx.in, sirgcdx.out | Sursă | Junior Challenge 2018 |
| Autor | Bogdan Pop | Adăugată de |  Junior Challenge •JuniorChallenge2018 |
| Timp execuţie pe test | 0.75 sec | Limită de memorie | 128000 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Sirgcdx
Dl.IOI, Nry şi Semicerc s-au săturat de probleme cu enunţuri lungi, care de fapt se dovedesc a fi EZ.Prin urmare,vă vor da un enunţ formal:
Numim un şir a şir gcd de lungime n dacă poate fi generat, pe baza unui alt sir b de lungime n, dupa aceasta regula:
a[ i ]=gcd(b[ 1 ],b[ 2 ],...b[ i ])
Funcţia gcd returneaza cel mai mare divizor al parametrilor.
De exemplu,şirul 6 3 3 este şir gcd deoarece este generat de sirul 6 9 24.
Numaraţi cate şiruri gcd de lungime N exista,având elemente între 1 si K,modulo 1.000.000.007.
Remarcaţi că nu contează în cate moduri acestea pot fi generate,conteaza doar cate siruri finale exista.
Date de intrare
Fişierul de intrare sirgcd.in conţine pe o singură linie numerele N şi K.
Date de ieşire
Fişierul de ieşire sirgcd.out conţine răspunsul, modulo 1.000.000.007.
Restricţii
- Subtask 1 (5 puncte): 1<=N,K<=5
- Subtask 2 (10 puncte): 1<=N,K<=102
- Subtask 3 (15 puncte): 1<=N,K<=103
- Subtask 4 (20 de puncte): 1<=N,K<=105
- Subtask 5 (20 de puncte): 1<=N<=109,1<=K<=105
- Subtask 6 (30 de puncte): 1<=N<=109,1<=K<=106
- Cine nu e cuminte şi întreabă de unde vine 'x'-ul din titlu e posibil să nu mai primească 100 de puncte.
Exemplu
| sirgcdx.in | sirgcdx.out |
|---|---|
| 3 2 | 4 |
| 31 17 | 72262 |
| 111 112 | 787881353 |
Explicaţie
Pentry primul exemplu,şirurile sunt: (2,2,2) , (2,2,1) , (2,1,1) , (1,1,1) .
Primul sir poate fi generat pe baza şirului (2,2,2), al doilea de şirul (2,2,1), al treilea de şirul (2,1,2), al patrulea de şirul (1,2,2).
Observaţi că există şi alte şiruri care pot genera unele din aceste şiruri (de exemplu (1,1,1) poate fi generat şi de şirul (1,2,1)).
