[ZJ][大數除法] a667. 可怕的除法＠Morris' Blog

2014-01-30 15:03:59| 人氣9,468| 回應0 | 上一篇 | 下一篇

[ZJ][大數除法] a667. 可怕的除法

推薦 0 收藏 0 轉貼0 訂閱站台

內容：

計算高精度除法的商、餘數（模）。（被除數≥0，除數＞0）

輸入說明：

輸入有多组測資（不多於11個）

每组測資有一行，第一個數為被除數，第二個數為除數。

輸出說明：

輸出被除數/除數和被除數%除數，中間空四個空格，詳細見範例。

範例輸入：

1212455 55555
5 6

範例輸出：

21    45800
0    5

使用萬進 + 二分

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
struct BigInteger {
   int val[500], len;
   BigInteger(char s[]) {
       memset(val, 0, sizeof(val));
       len = 0;
       int l = strlen(s), ten = 1;
       for(int i = l-1; i >= 0; i--) {
           if(ten == 10000)
               ten = 1, len++;
           val[len] = val[len] + (s[i] - '0')*ten;
           ten *= 10;
       }
   }
   BigInteger() {
       memset(val, 0, sizeof(val));
       len = 0;
   }
   void normal() {
       len = len + 10;
       while(len > 0 && val[len] == 0)
           len--;
   }
   void print() {
       printf("%d", val[len]);
       for(int i = len-1; i >= 0; i--)
           printf("%04d", val[i]);
   }
};
BigInteger divide(BigInteger a, BigInteger b) {
   int clen = max(a.len - b.len + 1, 0);
   BigInteger c;
   int buffer[505];
   c.len = clen;
   for(int i = clen; i >= 0; i--) {
       int l = 0, r = 9999, mid, result = 0;
       while(l <= r) {
           mid = (l+r) / 2;
           memset(buffer, 0, sizeof(buffer));
           for(int j = 0; j <= b.len; j++) {
               buffer[j+i] += b.val[j] * mid;
               if(buffer[j+i] >= 10000) {
                   buffer[j+i+1] += buffer[j+i]/10000;
                   buffer[j+i] %= 10000;
               }
           }
           int cmpflag = 0; // a ? buffer
           for(int j = a.len+1; j >= 0; j--) {
               if(a.val[j] > buffer[j])
                   cmpflag = 1, j = -1;
               else if(a.val[j] < buffer[j])
                   cmpflag = -1, j = -1;
           }
           if(cmpflag == 0) {result = mid;break;}
           if(cmpflag == 1)
               l = mid+1, result = mid;
           else
               r = mid-1;
       }
       c.val[i] = result;
       memset(buffer, 0, sizeof(buffer));
       for(int j = 0; j <= b.len; j++) {
           buffer[j+i] += b.val[j] * result;
           if(buffer[j+i] >= 10000) {
               buffer[j+i+1] += buffer[j+i]/10000;
               buffer[j+i] %= 10000;
           }
       }
       for(int j = 0; j <= a.len; j++) {
           a.val[j] -= buffer[j];
           while(a.val[j] < 0) {
               a.val[j+1] --;
               a.val[j] += 10000;
           }
       }
       a.normal();
   }
   c.normal();
   c.print();
   printf("    ");
   a.print();
   puts("");
   return c;
}
int main() {
   char s1[2048], s2[2048];
   while(scanf("%s %s", s1, s2) == 2) {
       BigInteger a(s1), b(s2);
       BigInteger c = divide(a, b);
   }
   return 0;
}

我要檢舉

#a667#可怕的除法#大數除法

台長： Morris

您可能對以下文章有興趣

[ZJ] a450. 棒棒糖比身高

a164. 區間最大連續和

[ZJ][0/1背包] a587. 祖靈好孝順 ˋˇˊ

d807. 方方

人氣(9,468) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 教育學習(進修、留學、學術研究、教育概況) | 個人分類: ZeroJudge |
此分類下一篇:[ZJ][遞迴] d734. 另类Hanoi
此分類上一篇:[ZJ] a812: 2013高雄市能力競賽高中組 3. 動物排隊

回應(0)