Articole

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 * 2 * 3 * 4 * 5 * 6 * 7 * … * 14 * … * 21 * … * 28 * … * 35 * … * 42 * … * 49 * … * 56 * … * 63 * … * 70 * … * 75\)
\(n!=1 * … * 1 * 7 * … * 2 * 7 * … * 3 * 7 * … * 4 * 7 * … * 5 * 7 * … * 6 * 7 * … * 7 * 7 * … * 8 * 7 * … * 9 * 7 *… * 7 * 10 * … * 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]+… \)
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…\cdot d_l^{e_l} \) unde \( d_1, d_2,…, d_l\) sunt factorii primi iar \( e_1, e_2,…, 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{\left\{{exp}_{n!}{\left(d_1^{e_1}\right)},{exp}_{n!}{\left(d_2^{e_2}\right)},{exp}_{n!}{\left(d_3^{e_3}\right)},…{exp}_{n!}{\left(d_l^{e_l}\right)}\right\}} \)(2)

Exemplu:
\( n=75, k=12\)
\( 12=2^2\cdot3 \)
\( {exp}_{75!}{\left(2^2\right)}=\left[\frac{{exp}_{75!}{\left(2\right)}}{2}\right]=\left(\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]\right)/2=\left(37+28+4+1+0\right)/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; }
________________________________________