Fişierul intrare/ieşire:perioada.in, perioada.outSursăAlgoritmiada 2011, Runda 1
AutorFilip Cristian BuruianaAdăugată dewefgefAndrei Grigorean wefgef
Timp execuţie pe test0.75 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Perioada

Mona si Lisa sunt impatimite ale jocurilor de noroc. In fiecare seara ele isi incearca sansa la o ruleta electronica speciala, care afiseaza la fiecare tura cate o litera mica a alfabetului englez. Cele doua fete au jucat noaptea trecuta N ture, pariind pe exact o litera in fiecare tura. Deoarece au pierdut o suma foarte mare de bani (in dolari), fetele se gandesc ca ruleta trebuie sa fie masluita si doresc sa demonstreze stiintific acest lucru. Ele au notat pe o foaie N caractere, al i-lea caracter reprezentand litera afisata de ruleta la cea de a i-a tura. Mona observa ca unele secvente de caractere aflate pe pozitii consecutive sunt periodice, adica sunt formate prin concatenarea de cel putin doua ori a aceluiasi sir. De exemplu, sirurile abcabc si ananan sunt periodice, dar abac nu este. Lisa realizeaza ca ruleta este masluita daca aceasta a generat multe secvente periodice. Lisa alege astfel M secvente pentru care doreste sa determine daca sunt sau nu periodice. In cazul in care o secventa e periodica Lisa vrea sa stie in cate moduri poate fi obtinuta prin concatenarea aceluiasi sir.

Date de intrare

Fişierul de intrare perioada.in contine pe prima linie numarul N. Cea de a doua linie contine N caractere, cu semnificatia din enunt. Cea de a treia linie contine numarul M de secvente care trebuiesc testate. Pe fiecare dintre urmatoarele M linii se gaseste o pereche de numere naturale x y, despartite de exact un spatiu.

Date de ieşire

În fişierul de ieşire perioada.out vor fi afisate M numere intregi, valoarea de pe linia i reprezentand numarul de moduri in care poate fi considerata concatenare cea de a i-a secventa din fisierul de intrare.

Restricţii

  • 1 ≤ N, M ≤ 100 000
  • 1 ≤ x < y ≤ N

Exemplu

perioada.inperioada.out
10
ranananvvv
3
2 7
1 6
8 10
1
0
1

Explicaţie

Secventa ananan este formata prin repetarea de 3 ori a sirului an. Secventa ranana nu este periodica.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content