Advertisement
Guest User

Untitled

a guest
Mar 30th, 2017
85
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.10 KB | None | 0 0
  1. # include <iostream>
  2. # include <string>
  3. # include <cstring>
  4. using namespace std;
  5.  
  6. int a[1024], b[1024], c[1024], y[1024];
  7.  
  8. void print(int a[])
  9. {
  10. for (int i = a[0]; i >= 1; --i) {
  11. cout << a[i];
  12. }
  13. cout << endl;
  14. }
  15.  
  16. void sub(int a[], int b[], int d)
  17. {
  18. // 这是一个特殊的减法
  19. // 假设b后面补充了d个0后相减
  20. // 那么注意对齐!!!
  21. int i = d, j = 1;
  22. int v = 0;
  23. while (j <= b[0]) {
  24. if (a[i] < b[j]) {
  25. a[i] += 10;
  26. a[i + 1]--;
  27. }
  28. a[i] -= b[j];
  29. ++i;
  30. ++j;
  31. }
  32. while (a[a[0]] == 0 && a[0] != 1) --a[0];
  33. }
  34.  
  35. void add(int a[], int b[])
  36. {
  37. // a+=b
  38. // 要注意长度的处理!!!
  39. int len = a[0];
  40. if (b[0] > len) len = b[0];
  41.  
  42. int r = 0;
  43. for (int i = 1; i <= len; ++i) {
  44. a[i] = a[i] + r + b[i];
  45. r = a[i] / 10;
  46. a[i] %= 10;
  47. }
  48. if (r > 0) a[++len] = r;
  49. a[0] = len;
  50. }
  51.  
  52. bool check(int a[], int b[])
  53. {
  54. if (a[0] < b[0]) return true;
  55. if (a[0] > b[0]) return false;
  56. for (int i = a[0]; i >= 1; --i) {
  57. if (a[i] < b[i]) return true;
  58. if (a[i] > b[i]) return false;
  59. }
  60. return false;
  61. }
  62.  
  63. bool head_check(int a[], int b[])
  64. {
  65. // 这是一个特殊的check
  66. // 假设b后面补充了a[0]-b[0]个0后比较大小
  67. // 等价于把a和b高位对齐比较大小
  68. int i = a[0], j = b[0];
  69. while (j >= 1) {
  70. if (a[i] > b[j]) return false;
  71. if (a[i] < b[j]) return true;
  72. --i;
  73. --j;
  74. }
  75. return false;
  76. }
  77.  
  78. void divide(int a[], int b[], int c[])
  79. {
  80. c[0] = 1; c[1] = 0;
  81. y[0] = 1; y[1] = 1;
  82. while (!check(a, b)) {
  83. // 位数差
  84. int d = a[0] - b[0];
  85. // y总是10的幂,初始为0次幂
  86. // 这里要挑选新的y, 先把原来的置0
  87. y[y[0]] = 0;
  88. if (head_check(a, b)) {
  89. // 补充d个0太大时
  90. y[0] = d;
  91. } else {
  92. // 可以补充d个0时候,d可以为0
  93. y[0] = d + 1;
  94. }
  95. // 本次试减的y是10的y[0]-1次方
  96. y[y[0]] = 1;
  97. sub(a, b, y[0]);
  98. add(c, y);
  99. }
  100. }
  101.  
  102. void process(string s, int a[])
  103. {
  104. a[0] = s.size();
  105. for (int i = 0; i < s.size(); ++i) {
  106. a[a[0] - i] = s[i] - '0';
  107. }
  108. }
  109.  
  110. int main()
  111. {
  112. for (int i = 0; i < 1024; ++i) {
  113. a[i] = b[i] = c[i] = 0;
  114. }
  115. string s1, s2;
  116. cin >> s1 >> s2;
  117. process(s1, a);
  118. process(s2, b);
  119. divide(a, b, c);
  120. print(c);
  121. print(a);
  122. return 0;
  123. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement