Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2018-06-06 18:33:49.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:sirgcdx.in, sirgcdx.outSursăJunior Challenge 2018
AutorBogdan PopAdăugată deJuniorChallenge2018Junior Challenge JuniorChallenge2018
Timp execuţie pe test0.75 secLimită de memorie128000 kbytes
Scorul tăuN/ADificultateN/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
Cine întreabă de unde vine 'x'-ul din titlu nu mai primeşte 100 de puncte

Exemplu

sirgcdx.insirgcdx.out
This is some
text written on
multiple lines.
This is another
text written on
multiple lines.

Explicaţie

...

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?