Exponentul unui numărul natural într-un produsul factorial.

Există o serie de probleme pentru care rezolvarea lor se rezumă la aflarea exponentului unui număr dat $k,exp(k)$ , într-un produs factorial $(n!)$, fără a calcula acel produs.
O metodă naivă ar fi căutarea multiplior lui k mai mici sau egali cu n și de câte ori de divid acestia cu k.
Exemplu:
$n=75,k=7$
$n!=1\ast 2\ast 3\ast 4\ast 5\ast 6\ast 7\ast \dots \ast 14\ast \dots \ast 21\ast \dots \ast 28\ast \dots \ast 35\ast \dots \ast 42\ast \dots \ast 49\ast \dots \ast 56\ast \dots \ast 63\ast \dots \ast 70\ast \dots \ast 75$
$n!=1\ast \dots \ast 1\ast 7\ast \dots \ast 2\ast 7\ast \dots \ast 3\ast 7\ast \dots \ast 4\ast 7\ast \dots \ast 5\ast 7\ast \dots \ast 6\ast 7\ast \dots \ast 7\ast 7\ast \dots \ast 8\ast 7\ast \dots \ast 9\ast 7\ast \dots \ast 7\ast 10\ast \dots \ast 75$ $exp(7)=11$

O soluție ar fi parcurgerea intervalului $[k,n]$cu pasul $k$ și contorizarea multiplilor.

C++
______________________________
exp=0 for (int i=k;i<=n;i+=k) { int x=i; while(x%k==0) {exp++;x/=k;} } cout<<exp;
___________________________
Termenul dominant este T(n) ->n/k (algoritm linear).
O altă soluție ar fi folosirea unei formule de calcul a exponentului lui $k$ în $n!$ notat ${exp}_{n!}\left(k\right)$, numită formula lui Legendre.
Dacă numărul k este prim ${exp}_{n!}\left(k\right)=\left[\frac{n}{k}\right]+\left[\frac{n}{k^2}\right]+\left[\frac{n}{k^3}\right]+\dots$
Exemplu:$n=75,k=7$
${exp}_{75!}\left(7\right)=\left[\frac{75}{7}\right]+\left[\frac{75}{49}\right]+\left[\frac{75}{343}\right]=10+1+0=11$
Se poate deduce că după un anumit număr de pași raportul va deveni subunitar ceea ce determină că suma va avea un număr finit de termeni. Pornind de la această relație, valoarea acelui exponent se poate calcula însumând câturile împărțirilor succesive.

Implementarea C++.
________________________________________
exp=0 while(n>=k) { n=n/k; exp+=n; }
________________________________________
Termenul dominant este T(n) ->log(n) (algoritm logaritmic)
Dacă numărul $k$ este un număr compus și în descompunerea în factori primi se obține produsul $k=d_1^{e_1}\cdot d_2^{e_2}\cdot \dots \cdot d_l^{e_l}$ unde $d_1,d_2,\dots ,d_l$ sunt factorii primi iar $e_1,e_2,\dots ,e_l$ exponenții acestora, vom folosi relațiile matematice (1) și (2), unde:
${exp}_{n!}\left(d^e\right)=\left[\frac{{exp}_{n!}\left(d\right)}{e}\right]$(1)
${exp}_{n!}\left(k\right)=min\{{exp}_{n!}\left(d_1^{e_1}\right),{exp}_{n!}\left(d_2^{e_2}\right),{exp}_{n!}\left(d_3^{e_3}\right),\dots {exp}_{n!}\left(d_l^{e_l}\right)\}$(2)

Exemplu:
$n=75,k=12$
$12=2^2\cdot 3$
${exp}_{75!}\left(2^2\right)=\left[\frac{{exp}_{75!}\left(2\right)}{2}\right]=(\left[\frac{75}{2}\right]+\left[\frac{75}{4}\right]+\left[\frac{75}{8}\right]+\left[\frac{75}{16}\right]+\left[\frac{75}{32}\right]+\left[\frac{75}{64}\right]+\left[\frac{75}{128}\right])/2=(37+28+4+1+0)/2=35$.
${exp}_{75!}\left(3\right)=\left[\frac{75}{3}\right]+\left[\frac{75}{9}\right]+\left[\frac{75}{27}\right]+\left[\frac{75}{81}\right]=25+8+2+0=35$.
În concluzie,
 ${exp}_{75!}\left(12\right)=min(35,35)=35$

Implementare C++
________________________________________
int a,b,divi[100],puterea[100],poz,minim; int putere(int n,int p) { int x=0; while(n>p) { x+=n/p; n=n/p; } return x; } int main() { f>>b>>a; int d=2; while(d*d<=a) { if(a%d==0) { divi[++poz]=d; int c=0; while(a%d==0) { a/=d puterea[poz]++; }} d++; } if(a!=1) { divi[++poz]=a; puterea[poz]=1; } minim=1000000; for(int i=1;i<=poz;i++) { puterea[i]=putere(b,divi[i])/puterea[i]; if(minim>puterea[i]) minim=puterea[i]; } g << minim; return 0; }
________________________________________