Fişierul intrare/ieşire: | sirgcdx.in, sirgcdx.out | Sursă | Junior Challenge 2018 |
Autor | Bogdan Pop | Adăugată de | |
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 şir b de lungime N, după această regulă: ai = gcd(b1, b2, ..., bi). Funcţia gcd returnează cel mai mare divizor al parametriilor.
De exemplu, şirul 6 3 3 este şir-gcd deoarece este generat de şirul 6 9 24. Număraţi câte şiruri-gcd de lungime N există, având elemente între 1 şi K, modulo 1.000.000.007. Remarcaţi că nu contează în câte moduri acestea pot fi generate, contează doar câte şiruri finale exista.
Date de intrare
Fişierul de intrare sirgcdx.in conţine pe o singură linie numerele N şi K.
Date de ieşire
Fişierul de ieşire sirgcdx.out conţine răspunsul, modulo 1.000.000.007.
Restricţii
- Subtask 1 (testul 1) - 5 puncte (testul 1): 1 ≤ N, K ≤ 5
- Subtask 2 (testele 2 - 3) - 10 puncte (testele 2 şi 3): 1 ≤ N, K ≤ 102
- Subtask 3 (testele 4 - 6) - 15 puncte (testele 4-6): 1 ≤ N, K ≤ 103
- Subtask 4 (testele 7 - 10) - 20 de puncte (testele 7-10): 1 ≤ N, K ≤ 105
- Subtask 5 (testele 11 - 14) - 20 de puncte (testele 11-14): 1 ≤ N ≤ 109, 1 ≤ K ≤ 105
- Subtask 6 (testele 15 - 20) - 30 de puncte (testele 15-20): 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
Pentru primul exemplu,şirurile sunt: (2,2,2) , (2,2,1) , (2,1,1) , (1,1,1) .
Primul şir 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 dintre aceste şiruri (de exemplu (1,1,1) poate fi generat şi de şirul (1,2,1)).