Pagini recente » Cod sursa (job #2795404) | Cod sursa (job #893465) | Cod sursa (job #336557) | Cod sursa (job #2282242) | Cod sursa (job #3122788)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("adunare.in");
ofstream fout("adunare.out");
struct Node {
int val;
Node *next;
Node(int val = 0) : val(val), next(nullptr) {}
};
struct bignum {
int n;
Node *root;
bignum(int n = 0) : n(n) {
root = new Node();
}
};
void Insert(Node *root, int pos, char *s) {
if(pos >= 0) {
root->next = new Node();
root->val = s[pos] - '0';
Insert(root->next, pos - 1, s);
}
}
const int NMAX = 1e4 + 10;
void Read(bignum &a) {
char s[NMAX + 1];
fin >> s;
int n = strlen(s);
a = bignum(n);
Insert(a.root, n - 1, s);
}
void Write(Node *root) {
if(root->next != nullptr) {
Write(root->next);
fout << root->val;
}
}
void Write(bignum a) {
Write(a.root);
}
void Deb(Node *root) {
if(root->next != nullptr) {
Deb(root->next);
cout << root->val;
}
}
void Deb(bignum a) {
Deb(a.root);
}
bignum operator + (bignum a, bignum b) {
bignum d(max(a.n, b.n));
bignum c = d;
int t = 0;
for(int i = 0; i < c.n; i++) {
int A = 0;
int B = 0;
if(a.root->next != nullptr) {
A = a.root->val;
a.root = a.root->next;
}
if(b.root->next != nullptr) {
B = b.root->val;
b.root = b.root->next;
}
t += A + B;
c.root->val = t % 10;
t /= 10;
c.root->next = new Node();
c.root = c.root->next;
}
while(t) {
c.n++;
c.root->val = t % 10;
t /= 10;
c.root->next = new Node();
c.root = c.root->next;
}
return d;
}
int Compare(bignum a, bignum b) {
if(a.n > b.n) {
return 1;
} else if(a.n < b.n) {
return -1;
} else {
int pos = -1, A, B;
for(int i = 0; i < a.n; i++) {
if(a.root->val != b.root->val) {
pos = i;
A = a.root->val;
B = b.root->val;
}
}
if(pos == -1) {
return 0;
} else {
if(A > B) {
return 1;
} else {
return -1;
}
}
}
}
bignum operator - (bignum a, bignum b) {
if(Compare(a, b) == -1) {
swap(a, b);
}
bignum d(max(a.n, b.n));
bignum c = d;
int t = 0;
for(int i = 0; i < c.n; i++) {
int A = 0;
int B = 0;
if(a.root->next != nullptr) {
A = a.root->val;
a.root = a.root->next;
}
if(b.root->next != nullptr) {
B = b.root->val;
b.root = b.root->next;
}
t += A - B;
c.root->val = t % 10;
t /= 10;
if(c.root->val < 0) {
c.root->val += 10;
t--;
}
c.root->next = new Node();
c.root = c.root->next;
}
int pos = -1;
bignum e = d;
c.root = d.root;
for(int i = 0; i < e.n; i++) {
if(d.root->val != 0) {
c.root = d.root->next;
pos = i;
}
d.root = d.root->next;
}
if(pos == -1) {
c.root = c.root->next;
pos = 1;
}
e.n = pos;
c.root->next = nullptr;
delete c.root->next;
return e;
}
bignum operator * (bignum a, bignum b) {
bignum d(a.n + b.n);
bignum c = d;
for(int i = 0; i < d.n; i++) {
c.root->val = 0;
c.root->next = new Node();
c.root = c.root->next;
}
bignum x = a;
bignum y = b;
for(int i = 0; i < a.n; i++) {
c = d;
for(int k = 0; k < i; k++)
c.root = c.root->next;
y = b;
for(int j = 0; j < b.n; j++) {
c.root->val += x.root->val * y.root->val;
c.root = c.root->next;
y.root = y.root->next;
}
x.root = x.root->next;
}
c = d;
int t = 0;
for(int i = 0; i < c.n; i++) {
t += c.root->val;
c.root->val = t % 10;
c.root = c.root->next;
t /= 10;
}
while(t) {
c.root->next = new Node();
c.root->val = t % 10;
t /= 10;
}
int pos = -1;
bignum e = d;
c.root = d.root;
for(int i = 0; i < e.n; i++) {
if(d.root->val != 0) {
c.root = d.root->next;
pos = i;
}
d.root = d.root->next;
}
if(pos == -1) {
c.root = c.root->next;
pos = 1;
}
e.n = pos;
c.root->next = nullptr;
delete c.root->next;
return e;
}
int main() {
bignum a, b;
Read(a);
Read(b);
Write(a + b);
return 0;
}