Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- # include <iostream>
- # include <string>
- # include <cstring>
- using namespace std;
- int a[1024], b[1024], c[1024], y[1024];
- void print(int a[])
- {
- for (int i = a[0]; i >= 1; --i) {
- cout << a[i];
- }
- cout << endl;
- }
- void sub(int a[], int b[], int d)
- {
- // 这是一个特殊的减法
- // 假设b后面补充了d个0后相减
- // 那么注意对齐!!!
- int i = d, j = 1;
- int v = 0;
- while (j <= b[0]) {
- if (a[i] < b[j]) {
- a[i] += 10;
- a[i + 1]--;
- }
- a[i] -= b[j];
- ++i;
- ++j;
- }
- while (a[a[0]] == 0 && a[0] != 1) --a[0];
- }
- void add(int a[], int b[])
- {
- // a+=b
- // 要注意长度的处理!!!
- int len = a[0];
- if (b[0] > len) len = b[0];
- int r = 0;
- for (int i = 1; i <= len; ++i) {
- a[i] = a[i] + r + b[i];
- r = a[i] / 10;
- a[i] %= 10;
- }
- if (r > 0) a[++len] = r;
- a[0] = len;
- }
- bool check(int a[], int b[])
- {
- if (a[0] < b[0]) return true;
- if (a[0] > b[0]) return false;
- for (int i = a[0]; i >= 1; --i) {
- if (a[i] < b[i]) return true;
- if (a[i] > b[i]) return false;
- }
- return false;
- }
- bool head_check(int a[], int b[])
- {
- // 这是一个特殊的check
- // 假设b后面补充了a[0]-b[0]个0后比较大小
- // 等价于把a和b高位对齐比较大小
- int i = a[0], j = b[0];
- while (j >= 1) {
- if (a[i] > b[j]) return false;
- if (a[i] < b[j]) return true;
- --i;
- --j;
- }
- return false;
- }
- void divide(int a[], int b[], int c[])
- {
- c[0] = 1; c[1] = 0;
- y[0] = 1; y[1] = 1;
- while (!check(a, b)) {
- // 位数差
- int d = a[0] - b[0];
- // y总是10的幂,初始为0次幂
- // 这里要挑选新的y, 先把原来的置0
- y[y[0]] = 0;
- if (head_check(a, b)) {
- // 补充d个0太大时
- y[0] = d;
- } else {
- // 可以补充d个0时候,d可以为0
- y[0] = d + 1;
- }
- // 本次试减的y是10的y[0]-1次方
- y[y[0]] = 1;
- sub(a, b, y[0]);
- add(c, y);
- }
- }
- void process(string s, int a[])
- {
- a[0] = s.size();
- for (int i = 0; i < s.size(); ++i) {
- a[a[0] - i] = s[i] - '0';
- }
- }
- int main()
- {
- for (int i = 0; i < 1024; ++i) {
- a[i] = b[i] = c[i] = 0;
- }
- string s1, s2;
- cin >> s1 >> s2;
- process(s1, a);
- process(s2, b);
- divide(a, b, c);
- print(c);
- print(a);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement