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(b1,b2,...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
Exemplu
| sirgcdx.in | sirgcdx.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicaţie
...
