這次直接使用大數除法來運算
1. 取得a及b的位數數目len_a、len_b
2. 將乘數b乘上10的 (len_a - len_b) 次方，也就是前移(len_a-len_b)位
3. 由i=0開始將a和b*i比較，找出滿足b*i≦A＜B*(i+1)的i
4. 商的 len_a-len_b+1位 ( 即 c[len_a-len_ b ) 就是i， a = a - b*i ，b=b/10
5. 重複直到 len_a - len_b==0
//Big number : http://www.csie.ntnu.edu.tw/~u91029/BigNumber.html
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <cstdio>
#include <cstring>
#include <iostream>
#define maxn 10000
using namespace std;
int len_a,len_b; //a和b的長度
void print(int a[maxn]){
int i=maxn-1; // 要印的數字位置
while(i>=0 && a[i]==0) i--; // 數字開頭的零都不印
if(i<0)cout << '0';
else while(i>=0) cout << a[i--];
}
// a > b or a < b
int compare(int a[maxn], int b[maxn])
{
for (int i=maxn-1; i>=0; i--) // 從高位數開始比，對應的位數相比較。
if (a[i] != b[i] && a[i] > b[i]){ // 發現 a b 不一樣大，馬上回傳結果。
return 1; // 1 = a>b
}
else if (a[i] != b[i] && a[i] < b[i]){
return 2; // 2 = a<b
}
return false; // 完全相等
}
// c = a + b;
void add(int a[maxn], int b[maxn], int c[maxn])
{
for (int i=0; i<maxn; i++) // 對應的位數相加
c[i] = a[i] + b[i];
for (int i=0; i<maxn-1; i++) // 一口氣進位
{
c[i+1] += c[i] / 10; // 進位
c[i] %= 10; // 進位後餘下的數
}
}
// c = a - b
void sub(int a[maxn], int b[maxn], int c[maxn])
{
//code優化
int max;
if(len_a>=len_b)max=len_a;
else max = len_b;
for (int i=0; i<max; i++) // 對應的位數相加
c[i] = a[i] - b[i];
for (int i=0; i<max-1; i++) // 一口氣補位
{
if(c[i]<0){
c[i] += 10;
c[i+1] --;
}
}
}
// c = a * b;
void mul(int a[maxn], int b[maxn], int c[maxn])
{
//code優化
int max;
if(len_a>=len_b)max=len_a;
else max = len_b;
for (int i=0; i<max; i++)
c[i] = 0;
for (int i=0; i<max; i++)
for (int j=0; j<max; j++)
if (i+j < max)
c[i+j] += a[i] * b[j];
for (int i=0; i<max-1; i++) // 一口氣進位
{
c[i+1] += c[i] / 10;
c[i] %= 10;
}
}
// c = a / b
void div(int a[maxn], int b[maxn], int c[maxn])
{
//code 優化
int max=0;
if(len_a>=len_b)max=len_a+1;
else max = len_b+1;
int t[maxn]={0};
int t2[maxn]={0};
int b2[maxn]={0};
int b3[maxn]={0};
int len_diff = len_a-len_b; //兩數字位數差 difference of length
memset(t,0,sizeof(t));
t[len_diff]=1; //t陣列的用意是，創造一個"...001000..."的陣列，好讓除數可以乘上
while(len_diff >= 0){
memset(b2,0,sizeof(b2));
mul(b,t,b2); //b2 = b * t
for(int i=9;i>0;i--){ //商數由9→1
memset(b3,0,sizeof(b3));
for(int j=max-1;j>=0;j--){
b3[j] = b2[j] * i; // b3 = b2 * i ，測試商數
}
for(int j=0;j<max;j++){
while(b3[j]>=10){ //所有位數進位
b3[j]-=10;
b3[j+1]+=1;
}
}
if(compare(a,b3)==1 || compare(a,b3)==0){ //若a>=b3
c[len_diff]+=i; // 於len_diff的商數+1
sub(a,b3,t2); // t2 = a - b3
for(int j=0;j<max;j++)a[j]=t2[j]; //a = t2
memset(t2,0,sizeof(t2));
}
}
memset(t,0,sizeof(t));
len_diff--; //位數往前一位
if(len_diff>=0)t[len_diff]=1;
}
}
void mod(int a[maxn], int b[maxn], int c[maxn])
{
//code 優化
int max=0;
if(len_a>=len_b)max=len_a;
else max = len_b;
int t[maxn]={0};
int t2[maxn]={0};
int b2[maxn]={0};
int b3[maxn]={0};
int len_diff = len_a-len_b; //兩數字位數差
t[len_diff]=1;
while(len_diff>=0){
memset(b2,0,sizeof(b2));
mul(b,t,b2);
for(int i=9;i>0;i--){
memset(b3,0,sizeof(b3));
for(int j=max-1;j>=0;j--){
b3[j] = b2[j] * i;
while(b3[j]>=10){
b3[j]-=10;
b3[j+1]+=1;
}
}
if(compare(a,b3)==1 || compare(a,b3)==0){
sub(a,b3,t2);
for(int j=0;j<max;j++)a[j]=t2[j]; // a = t2
for(int j=0;j<max;j++)c[j]=t2[j]; // c = t2
memset(t2,0,sizeof(t2));
}
}
memset(t,0,sizeof(t));
len_diff--;
if(len_diff>=0)t[len_diff]=1;
}
}
char input_a[maxn]={'\0'};
char op,op1,op2,op3;
char input_b[maxn]={'\0'};
int a[maxn],b[maxn],result[maxn];
int main(){
freopen("input.txt","r",stdin);
while(scanf("%s%s%s",&input_a,&op2,&input_b)!=EOF){
memset(a,'\0',sizeof(a));
memset(b,'\0',sizeof(b));
memset(result,'\0',sizeof(result));
//printf("%s %c %s\n",input_a,op2,input_b);
//轉換為倒轉數字陣列
len_a = strlen(input_a);
for(int i=0;i<len_a;i++){
a[i]=input_a[len_a-i-1]-48;
}
len_b = strlen(input_b);
for(int i=0;i<len_b;i++){
b[i]=input_b[len_b-i-1]-48;
}
if(op2=='/'){
if(compare(a,b)==2)printf("0"); //若b>a，則為0
else if(len_b==1 && b[0]==0)break;
else {
div(a,b,result);
print(result);
}
}
if(op2=='%'){
if(compare(a,b)==2)print(a); //若b>a，餘數則為a
else {
mod(a,b,result);
print(result);
}
}
printf("\n");
}
return 0;
}
