信息学奥赛练习题: 高精除。
【题目描述】
高精除以高精,求它们的商和余数。
【输入】
输入两个低于300位的正整数。
【输出】
输出商和余数。
【输入样例】
1231312318457577687897987642324567864324567876543245671425346756786867867867
1231312318767141738178325678412414124141425346756786867867867
【输出样例】
999999999748590
179780909068307566598992807564736854549985603543237528310337
参考代码:
#include <bits/stdc++.h> using namespace std; #define N 305 struct HPN { int a[N];//数字数组 HPN() { memset(a, 0, sizeof(a)); } HPN(char s[]) { memset(a, 0, sizeof(a)); a[0] = strlen(s); for(int i = 1; i <= a[0]; ++i) a[i] = s[a[0] - i] - '0'; } void show() { for(int i = a[0]; i >= 1; --i) cout << a[i]; cout << endl; } int& operator [] (int i)//类似数组取值 { return a[i]; } int numcmp(int a[], int b[]) { if(a[0] > b[0])//如果a的位数比较多 return 1; else if (a[0] < b[0])//如果b的位数比较多 return -1; else { for(int i = a[0]; i >= 1; --i) { if(a[i] > b[i]) return 1; else if(a[i] < b[i]) return -1; } return 0; } } bool operator >= (HPN b) { return numcmp(a, b.a) >= 0; } void setLen(int i)//从第i位置开始,向低位寻找,直到找到一个不为0的数位,更新数字长度 { while(a[i] == 0 && i > 1) i--; a[0] = i; } void operator -= (HPN b) { int i; for(i = 1; i <= a[0] || i <= b[0]; ++i) { if(a[i] < b[i]) { a[i + 1]--; a[i] += 10; } a[i] -= b[i]; } setLen(i); } void addNum(int num)//a = a * 10 + num { if(a[0] == 1 && a[1] == 0)//如果a是0,那么就把个位设为num a[1] = num; else { for(int i = a[0]; i >= 1; --i)//数组移位 a[i+1] = a[i]; a[1] = num; a[0]++; } } HPN operator / (HPN b) //高精除高精 { HPN r, x;//r:商 x:余数 int i; for(i = a[0]; i >= 1; --i) {//以下几句完成x = x * 10 + a[i] x.addNum(a[i]); //求r[i] = x / b; 以减法代替除法 int q = 0;//记录减了几次,该值就是通过减法代替除法得到的商 while(x >= b)//高精度数字比较 { x -= b;//高精度数字减法 q++; } r[i] = q; } r.setLen(a[0]); return r; } HPN operator % (HPN b) //高精模高精 { HPN x; for(int i = a[0]; i >= 1; --i) { //以下几句完成x = x * 10 + a[i] x.addNum(a[i]); while(x >= b)//高精度数字比较 x -= b;//高精度数字减法 } return x; } }; int main() { char s1[N], s2[N]; cin >> s1; cin >> s2; HPN n1(s1), n2(s2), n3, n4; n3 = n1 / n2; n3.show(); n4 = n1 % n2; n4.show(); return 0; }