Fişierul intrare/ieşire:matrita.in, matrita.outSursăJunior Challenge 2018
AutorAndrei ComanAdăugată deJuniorChallenge2018Junior Challenge JuniorChallenge2018
Timp execuţie pe test1 secLimită de memorie524288 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Matrita

Plictisit de înmulţirea polinoamelor în timp liniar, de rezolvarea conjecturilor sau a altor banalităţi precum “Traveling salesman problem”, Nry s-a decis să pornească în căutarea secretului fericirii eterne. Privind însa în jurul său, a constatat cu stupoare că olimpicii recurg la tehnici necurate în acest joc pentru satisfacţie, de la sustrasul subtil al surselor sau al ideilor de probleme, până la acte mult mai grave, precum însuşirea locurilor la IOI sau a ediţiilor precedente de Junior Challenge. Dorind însă să fie original (şi să păstreze în acelaşi timp noua tradiţie), Nry a ajuns la următoarea concluzie: trebuie să subtilizeze Matriţa!

Odată ajuns în posesia elixirului magic, acesta l-a aşezat într-un colţ al Beciului Olimpic (unul din cele mai sigure adăposturi, în care duşmanii pot pătrunde doar prin tavanul de sticlă). Însă, pentru a se asigura că noua sa achiziţie nu va dispărea în mod neaşteptat, acesta a decis să formeze un sistem de apărare în modul următor: el a privit Beciul ca o matrice pătratica de latură N + 1 (liniile şi coloanele sunt numerotate de la 0 la N), Matriţa aflându-se în pătratul aflat pe linia 0 şi coloana 0. El doreşte să plaseze mai multe capcane în pătrate cu indicii liniilor şi al coloanelor cuprinşi intre 1 şi N, astfel încât fiecare capcană să fie vizibilă din punctul în care se află Matriţa (cu alte cuvinte, să nu existe două capcane situate în (l1, c1), respectiv (l2, c2) şi un număr real k cu proprietatea că x1 = x2 * k si y1 = y2 * k).

Nry vă roagă să răspundeţi la următoarea întrebare: ştiind numărul N, în câte moduri îşi poate construi el sistemul de apărare al Matriţei? Răspunsul trebuie afişat modulo MOD.

Date de intrare

Fişierul de intrare matrita.in conţine o singura linie pe care sunt scrise doua numere, N şi MOD, cu semnificaţia din enunţ.

Date de ieşire

În fişierul de ieşire matrita.out veţi afişa un singur număr natural, şi anume răspunsul cerinţei modulo MOD.

Restricţii

  • Nry dispune de un număr nelimitat de capcane
  • Fiind foarte paranoic, acesta va plasa întotdeauna cel putin o capcana
  • 1 ≤ N ≤ 12.000.000
  • 100.000.000 ≤ MOD ≤ 1.000.001.000
  • Subtask 1 (testele 1 - 2) - 10 puncte: N ≤ 1.800
  • Subtask 2 (testele 3 - 4)- 5 puncte: N ≤ 3.000
  • Subtask 3 (testele 5 - 7)- 5 de puncte: N ≤ 4.000
  • Subtask 4 (testele 8 - 12)- 30 de puncte: N ≤ 300.000
  • Subtask 5 (testele 13 - 17)- 10 de puncte: N ≤ 750.000
  • Subtask 6 (testele 18 - 22)- 25 puncte: N ≤ 6.500.000
  • Subtask 7 (testele 23 - 27)- 5 puncte: N ≤ 10.000.000
  • Subtask 8 (testele 28 - 30)- 10 puncte: N ≤ 12.000.000
  • Legenda spune ca oricine gusta din Matriţă are un loc asigurat la IOI 2020

Exemplu

matrita.inmatrita.out
1 1000000007
1
2 1000000007
11
5 1000000007
3538943
768325 1000000007
667479250

Explicaţie

Pentru primul exemplu, el poate doar sa amplaseze o capcana in patratul (1, 1).

Pentru cel de-al doilea exemplu, sunt valide urmatoarele configuratii:
{(1, 1)}, {(1, 1), (1, 2)}, {(1, 1), (2, 1)}, {(1, 1), (1, 2), (2, 1)},
{(2, 2)}, {(2, 2), (1, 2)}, {(2, 2), (2, 1)}, {(2, 2), (1, 2), (2, 1)},
{(1, 2)}, {(2, 1)}, {(1, 2), (2, 1)}.
Configuratia {(1, 1), (2, 2)} nu poate fi aleasa deoarece capcana (2, 2) nu este vizibila.

Nry considera că o explicaţie a ultimelor două exemple ar fi inadecvat de lunga.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?