2014-01-30 15:03:59Morris
[ZJ][大數除法] a667. 可怕的除法
內容 ：
計算高精度除法的商、餘數（模）。（被除數≥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;
}