Lista de probleme 3

Ștefan Vodă, după bătălia de la Vaslui, și-a aliniat cei n oșteni și a dat fiecăruia câte un număr natural nenul a0, a1, … an-1. Având o bună dispoziție după strașnica victorie, voievodul face două tipuri de operații:

• 1 i x (aceasta este primeneala!): oșteanul de la poziția i primește o nouă valoare (ai devine egal cu x);
• 2 x y d (aceasta este iscoditura!): câte numere din secvența de oșteni ax, ax+1, …, ay au cel mult d divizori?

Scrieți un program care răspunde corect la toate iscoditurile și veți fi la fel de faimoși ca Ștefan cel Mare!

Spunem că un număr natural x este fibopower dacă acesta se poate descompune în produs de trei numere Fibonacci distincte. Se consideră șirul A = (A[1], A[2], ..., A[n] cu n elemente numere naturale nenule, respectiv un număr natural k cuprins între 1 și n. O secvență a șirului A este formată din valori situate pe poziții consecutive în A: A[i], A[i+1], ..., A[j], unde 1 ≤ i ≤ j ≤ n. Pe șirul A se fac q interogări de tipul x y cu semnificația: să se determine numărul secvențelor A[i], A[i+1], ..., A[j] cu x ≤ i ≤ j ≤ y care conțin exact k numere fibopower. Fiind cunoscute n, k, q și cele n elemente ale șirului A, să se determine răspunsul pentru cele q interogări date.

Octav începe din colțul stânga-sus al foii de matematică (pătrăţelul 1, 1) și merge diagonal în jos, marcând cu x fiecare pătrățel prin care trece. Când ajunge la una dintre marginile foii, el schimbă direcţia şi sensul de deplasare. El se deplasează continuu, marcând cu x pătrăţelele prin care trece, până când ajunge din nou într-un colț al foii. Octav consideră că pătrăţelele marcate cu x sunt ziduri. Pătrăţelele marcate cu x delimitează pe foaia de matematică diferite modele geometrice. p. Cunoscând numerele naturale N şi M, scrieţi un program care să rezolve următoarele cerinţe:
1. determină numărul de pătrăţele marcate cu x;
2. determină numărul total de modele obţinute;
3. determină numărul de categorii obţinute;
4. determină descrierile categoriilor de modele obţinute, ordonate crescător după pătrăţelul reprezentativ.