Fişierul intrare/ieşire:shukarime.in, shukarime.outSursăConcursul National de Informatica "Adolescent Grigore Moisil" 16
AutorTeodor IonescuAdăugată deAGMinformaticaAGMInformatica AGMinformatica
Timp execuţie pe test2 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Shukarime

Cu ocazia impinirii centenarului de la publicarea teoriei relativitatii generale, Gheorghe Fierar demonteaza rand pe rand, intr-o declaratie in exclusivitate la Digi 23 Puncte, teoriile fratiorului Albert. Printre acuzatiile aduse de excelenta sa se numara si plagiatul privind faimoasa ecuatie E = mc2, care de fapt apare pentru prima data in lucrarile poetului nepereche sub forma E = albastra*dulcefloare. Automat si calculele privind viteza undei gravitationale sunt gresite fiind compuse de "un alienat". Din fericire, geometria versificatiei in poezie ne permite sa deducem ecuatia V=FG, unde cu G este notata constanta omului de geniu, iar cu F frecventa vrajelii existentei efemere.

Un impatimit telespectator al postului mentionat, Calif Gutzanu intelege exceptionalitatea dezvaluirilor domnului Fieraru si isi da seama ca intr-o zi va deveni faimos si va revolutiona fizica moderna daca va reusi sa confirme experimental ecuatia. Pentru a putea face rost de date experimentale insa, Calif Gutzanu are nevoie de cel putin doua gauri negre pentru a putea masura cu exactitate malformatiile spatiu-timp. Zis si facut, domnul Gutzanu "imprumuta" un interferometru din laboratorul facultatii si se instaleaza la Dristor pentru ca, zice acesta, cea mai instabila substanta din Univers capabila sa genereze spontan gauri negre este chiar shaorma produsa strict de acestia. Pe masura ce shaorma se dezintegreaza, Gutzanu noteaza N valori rezultate in sirul v1, v2, … vN, frecventele emise de shaorma. Cunoscand constanta G, acesta se intreaba acum cate perechi [st,dr] cu st ≤ dr exista in sir cu proprietatea ca produsul secventei vst * vst+1 * … * vdr-1 * vdr poate fi scris ca FG, unde F este o variabila oarecare. Daca acest numar este prea mic, experimentul va trebui reluat cu mai multa maioneza si sos picant.

Date de intrare

Pe prima linie a fisierului de intrare se gaseste T, numarul de teste. Pe prima linie a fiecarui test se afla numerele N si G, urmand ca pe linia imediat urmatoare sa fie descris sirul v1, v2, … vN.

Date de ieşire

In fisierul de iesire se vor afisa T linii, pe fiecare dintre acestea un intreg reprezetand numarul de perechi cerut.

Restricţii

  • 1 ≤ T ≤ 5
  • 1 ≤ N ≤ 105
  • 1 ≤ G ≤ N
  • 1 ≤ vi ≤ 106

Exemplu

shukarime.inshukarime.out
2
6 2
7 6 15 5 3 2
6 2
2 17 2 1 23 23
1
3

Explicaţie

In primul exemplu produsul secventei cuprinse intre pozitiile [3,5] este 225 si este singurul ce poate fi scris ca 225=15G=152.
In exemplul al doilea secventele sunt [4,4], [4,6], [5,6].

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?