Candale Silviu (silviu) Considerăm problema #biprime :
Se dă \( n \) un număr natural care este produsul a două numere prime distincte și \( m \) reprezentând numărul numerelor mai mici sau egale cu n, prime cu n. Aflați cele două numere prime din descompunerea lui \( n \). \( 1 ≤ m ≤ n ≤ 10^{25} \)
Soluție
Valorile mari ale lui \( n \) și \( m \) nu permit aplicarea de descompunere în factori. De fapt, valorile date depășesc valorile maxime ale tipurilor întregi reprezentate pe 64 de biți (unsigned long long in C++).
Proprietățile particulare ale acestor valori permit o rezolvare bazată pe obseervații matematice.
Fie \( x \) și \( y \), \(x < y\) cele două numere care intervin în descompunerea lui \( n \). Atunci avem:
$$ \begin{cases} x \cdot y = n \\ \varphi(n) = m \end{cases} $$
Dar \( \varphi(n) = n (1 – \frac{1}{x}) (1 – \frac{1}{y}) = x \cdot y \cdot \frac{x-1}{x} \cdot \frac{y-1}{y} = (x-1) \cdot (y-1) \), deci \( (x-1) \cdot (y-1) = m \), \( xy-x-y+1 = m \).
Obținem astfel un sistem:
$$ \begin{cases} x \cdot y = n\\ xy-x-y+1 = m\end{cases}$$
adică
$$ \begin{cases} x \cdot y = n\\ x+y = n-m+1\end{cases}$$
Exprimându-l pe \(y\) din a doua ecuație și înlocuind în prima obținem ecuația de gradul II:
$$ x^{2} – (n-m+1) \cdot x + n = 0 $$
În care \( a = 1, b = -(n – m +1), c = n \). O rezolvăm.
$$ \Delta = b^{2} – 4ac $$
Ecuația are două soluții pozitive. O vom deterina pe cea mai mică, deoarece am fixat \(x < y\) (cealaltă soluție a ecuației va da pereche în care \( x > y\)).
$$ x = \frac{-b – \sqrt{\Delta}}{2 \cdot a} $$
Algoritm
O reprezentare în pseudocod a algortmului de rezolvare este
citeste n , m a ← 1 b ← -(n-m+1) c ← n delta ← b*b-4*a*c x ← (-b - sqrt(delta)) / (2*a) y ← n - x scrie x,y
Sursă C++
Restricțiile din enunț (n,m ≤ 1025) nu permit scrierea unui program C++ care folosește doar simple de date, fiind necesară implementarea numerelor mari. Soluția de mai jos obține punctaj parțial.
#include <iostream>
#include <cmath>
using namespace std;
int main()
{
long long n,m,x,y,a,b,c,rdelta;
cin >> n >> m;
a = 1, b = -(n-m+1), c = n;
rdelta = sqrt(1.0*b*b - 4.0*a*c);
x = (-b - rdelta) / (2*a);
y = n / x;
cout << x << ' ' << y;
return 0;
}