Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2018-06-07 12:37:56.
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(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.insirgcdx.out
3 24
31 17

Explicaţie

Pentry primul exemplu,şirurile sunt: (2,2,2) , (2,2,1) , (2,1,1) , (1,1,1) .

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?