h1. 'Dreptunghi':problema/dreptunghi
Vom aplica un algoritm similar cu 'Algoritmul lui Euclid':problema/euclid2 pentru determinarea celui mai mic divizor comun. Pentru fiecare dreptunghi de $N x M$, voi considera că N ≤ M. Vom crea un număr maxim de pătrate de dimensiune $N x N$. Acest număr maxim de pătrate este egal cu $[M / N]$, iar pentru fiecare din aceste pătrate vom folosi exact $N$ operaţii. Astfel, vom completa un dreptunghi de dimensiune $[M / N]*N x N$. Mai rămâne să completăm un dreptunghi de dimensiune $N x M%N$. Vom aplica acelaşi procedeu şi pentru acest dreptunghi, până când terminăm de completat tot dreptunghiul iniţial.
Vom aplica un algoritm similar cu 'Algoritmul lui Euclid':problema/euclid2 pentru determinarea celui mai mic divizor comun. Pentru fiecare dreptunghi de $N x M$, voi considera că $N ≤ M$. Vom crea un număr maxim de pătrate de dimensiune $N x N$. Acest număr maxim de pătrate este egal cu $[M / N]$, iar pentru fiecare din aceste pătrate vom folosi exact $N$ operaţii. Astfel, vom completa un dreptunghi de dimensiune $[M / N]*N x N$. Mai rămâne să completăm un dreptunghi de dimensiune $N x M%N$. Vom aplica acelaşi procedeu şi pentru acest dreptunghi, până când terminăm de completat tot dreptunghiul iniţial.
h1. 'Sumfact':problema/sumfact
Soluţia se bazează pe faptul că pentru orice număr $X$, coeficientul lui $X!$ în descompunerea unui număr $N$ poate fi maxim $X$. Dacă acest coeficient este mai mare, de pildă $X+1$, vom avea $(X+1) * X! = (X+1)!$. Având în vedere că al doilea coeficient este mai mic, vom alege să folosim $(X+1)!$ pentru descompunerea lui $N$. Plecând de la această observaţie, vom parcurge factorialele de la cel mai mare la cel mai mic, vom afla coeficientul fiecăruia împărţind $N$ la acel factorial, urmând să scădem rezultatul din $N$ şi să continuăm procedeul până când $N$ devine $0$.
Soluţia se bazează pe faptul că pentru orice număr $X$, coeficientul lui $X!$ în descompunerea unui număr $N$ poate fi maxim $X$. Dacă acest coeficient este mai mare, de pildă $X+1$, vom avea $(X+1) * X! = (X+1)!$. Având în vedere că al doilea coeficient este mai mic, vom alege să folosim $(X+1)!$ pentru descompunerea lui $N$. Plecând de la această observaţie, vom parcurge factorialele de la cel mai mare la cel mai mic, vom afla coeficientul fiecăruia împărţind $N$ la acel factorial, urmând să scădem ce am obţinut din $N$ şi să continuăm procedeul până când $N$ devine $0$.
h1. 'K Aparitii':problema/aparitii
