Răspuns :
Răspuns:
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <cmath>
using namespace std;
#define lgmax 30
typedef string NrMare;
void citire(NrMare &x){
cin >> x;
}
void scadere(NrMare &a, NrMare b){
int carry = 0;
int i;
while(b.length() < a.length())
b = '0'+b;
for(i = a.length()-1; i >= 0; i--){
a[i] = a[i] - carry - b[i];
if(a[i] < 0){
a[i] += 10;
carry = 1;
} else carry = 0;
a[i] += '0';
}
}
void scadere(NrMare &a, unsigned long long int b){
int carry = 0;
int i;
for(i = a.length()-1; i >= 0; i--){
a[i] = a[i] - '0' - carry - b%10;
b/=10;
if(a[i] < 0){
a[i] += 10;
carry = 1;
} else carry = 0;
a[i] += '0';
}
}
void adunare(NrMare &a, int b){
int carry = 0,i;
for(i = a.length()-1; i >= 0; i--){
a[i] = a[i]-'0' + carry + b % 10;
b /= 10;
if(a[i] > 9){
carry = a[i] / 10;
a[i] %= 10;
}else carry = 0;
a[i] += '0';
}
}
void adunare(NrMare &a, NrMare b){
int carry = 0, i;
int Max = a.length() > b.length() ? a.length() : b.length();
while(a.length() < Max)
a = '0' + a;
while(b.length() < Max)
b = '0' + b;
for(i = Max-1; i >= 0; i--){
a[i] = a[i]- '0' + b[i] - '0' + carry;
if(a[i] > 9){
carry = a[i] / 10;
a[i] %= 10;
}else carry = 0;
a[i] += '0';
}
if(carry)
a[i] = carry;
}
void afisare(NrMare a){
int i;
for(i = 0; a[i] == '0'; i++);
for(; i < a.length(); i++)
cout << a[i];
}
void copie(NrMare &y, NrMare x){
y = x;
}
void citire_str(NrMare &x, string s){
x = s;
}
void sqrt(NrMare &x){
double n = stod(x);
double xk = 1;
for(int i = 0; i < 10000; ++i) {
xk = ( xk + n / xk ) / 2;
}
citire_str(x, to_string((unsigned long long)round(xk)));
}
string longDivision(string number, int divisor)
{
string ans;
int idx = 0;
int temp = number[idx] - '0';
while (temp < divisor)
temp = temp * 10 + (number[++idx] - '0');
while (number.size() > idx)
{
ans += (temp / divisor) + '0';
temp = (temp % divisor) * 10 + number[++idx] - '0';
}
if (ans.length() == 0)
return "0";
return ans;
}
string multiply(string num1, string num2)
{
int n1 = num1.size();
int n2 = num2.size();
if (n1 == 0 || n2 == 0)
return "0";
vector<int> result(n1 + n2, 0);
int i_n1 = 0;
int i_n2 = 0;
for (int i=n1-1; i>=0; i--)
{
int carry = 0;
int n1 = num1[i] - '0';
i_n2 = 0;
for (int j=n2-1; j>=0; j--)
{
int n2 = num2[j] - '0';
int sum = n1*n2 + result[i_n1 + i_n2] + carry;
carry = sum/10;
result[i_n1 + i_n2] = sum % 10;
i_n2++;
}
if (carry > 0)
result[i_n1 + i_n2] += carry;
i_n1++;
}
int i = result.size() - 1;
while (i>=0 && result[i] == 0)
i--;
if (i == -1)
return "0";
string s = "";
while (i >= 0)
s += std::to_string(result[i--]);
return s;
}
NrMare n(lgmax, '0'),m(lgmax, '0'),proc(lgmax, '0'),cache(lgmax, '0'),nori4(lgmax, '0'),a(lgmax, '0');
int main(){
citire(n);
citire(m);
copie(proc, n);// proc = n
scadere(proc, m);// proc = n - m
adunare(proc, 1);// proc = n - m + 1 = c
copie(cache, proc);// cache = c
cache = multiply(cache, cache);// cache = c^2
copie(nori4, n);// nori4 = n
nori4 = multiply(nori4, "4");// nori4 = 4n
scadere(cache, nori4);// cache = c^2 - 4n
sqrt(cache);// cache = sqrt(c^2 - 4n)
copie(a,proc);// a = c
scadere(a, cache);// a = c - sqrt(c^2 - 4n)
cout << longDivision(a,2) << ' ';// afisam ( c-sqrt(c^2-4n) ) / 2 (a-ul)
copie(a,proc);// a = c
adunare(a,cache);// a = c + sqrt(c^2 - 4n)
cout << longDivision(a,2) << '\n'; // afisam ( c + sqrt(c^2 - 4n) )/ 2 (b-ul)
}
Explicație:
Se folosesc numere mari.
[tex] \varphi(n) = m, n = ab \implies m = (a-1)\cdot a^0\cdot (b-1)\cdot b^0 = (a-1)(b-1)\\ m = ab - a -b +1\\ \\ m = n - a - b + 1\\ \\ a+b = n-m+1\\ \\ \text{Notam c = n-m+1}\\ \\ \begin{cases}a+b = c\\ ab = n\end{cases}\\ \\ a = c - b\\ \\ (c-b)\cdot b = n\\ \\ cb - b^2 - n =0\\ \\ -b^2 + cb - n = 0\\ \\ b^2 -cb + n = 0\\ \\ \Delta = c^2 - 4n\\ \\ \sqrt{\Delta} = \sqrt{c^2-4n}\\ \\ a < b \implies a = \frac{c - \sqrt{c^2 - 4n}}{2}, b = \frac{c + \sqrt{c^2 - 4n}}{2}[/tex]
Vă mulțumim pentru vizita pe site-ul nostru dedicat Informatică. Sperăm că informațiile oferite v-au fost de ajutor. Nu ezitați să ne contactați pentru orice întrebare sau dacă aveți nevoie de asistență suplimentară. Vă așteptăm cu drag data viitoare și nu uitați să ne adăugați la favorite!