Lista de probleme 2

Alex este un băiat căruia îi place să citească și care contorizează cât de mult a citit pe parcursul ultimelor n zile. Mai precis, el și-a notat câte pagini a citit în fiecare dintre acestea. Chiar dacă pasiunea lui este literatura, își dorește să progreseze și la informatică. Alex și-a pus două întrebări legate de șirul format din numărul de pagini citite de el în ultimele n zile, dar după ce a petrecut câteva zile gândindu-se la ele și-a dat seama că sunt prea dificile pentru el. Ajutați-l să găsească răspunsurile! Fie numărul n, numărul p și acel șir de valori notate de Alex în cele n zile. Determinați răspunsul la următoarele întrebări care îl frământă pe Alex:

1) Câte triplete de numere aflate pe poziții consecutive în șirul dat îndeplinesc condiția ca cel mai mare divizor comun al lor să aibă cel mult p divizori naturali?
2) Care este lungimea maximă a unei secvențe din șirul dat, în care cel mai mare divizor comun al oricărui triplet de numere situate pe poziții consecutive are cel mult p divizori naturali?

Oglinditul unui număr natural x este numărul obținut prin parcurgerea cifrelor lui x de la dreapta la stânga, ignorându-se cifrele nule de pe ultimele poziții ale lui x. De exemplu, oglinditul lui 103 este 301, în timp ce oglinditul lui 2500 este 52. O pereche de numere naturale distincte x și y se numește pereche oglindită dacă atât x este oglinditul lui y, cât și y este oglinditul lui x. De exemplu, numerele x = 42 și y = 24 formează o pereche oglindită, însă numerele x = 1 și y = 100 nu formează o pereche oglindită. Un număr natural x este considerat palindrom dacă x este egal cu oglinditul său. De exemplu, numărul 42124 este palindrom. Din două numere distincte se poate forma un număr nou prin alipirea unuia la dreapta celuilalt. De exemplu, din numerele 124 și 42 se pot obține numerele 12442 (din alipirea lui 42 la dreapta lui 124) și 42124 (din alipirea lui 124 la dreapta lui 42). Fie un șir de numere naturale a[1], a[2], ..., a[n]. Determinați:

1) Numărul perechilor de indici (i, j), cu 1 ≤ i < j ≤ n, având proprietatea că a[i] și a[j] formează o pereche oglindită.
2) Cel mai mare număr palindrom care se poate forma prin alipirea a două numere distincte din șir.