rt,我的代码不开O2就能AC,开了O2反而WA,萌新刚学OI找不出来UB,求调
#include <bits/stdc++.h>
#define rep(a, b, c) for(register int a = b; a <= c; ++ a)
using namespace std;
struct BIGN {
static const int MAXN = 10005, ZIP = 4;
int POW;
string num, rem, tmp; //rem余数
int a[MAXN], cnt; //cnt储存压位后a最后一位的下标
inline void READ() { cin >> num; }
inline void WRITE() { cout << num; }
//压位专用
inline int toint(string x) {
int len = x.length(), res = 0;
rep(i, 0, len - 1) res = res * 10 + x[i] - '0';
return res;
}
//压4位,将运算后的整数数组转为字符串
inline string tostr(int x) {
string res;
while(x) res += x % 10 + '0', x /= 10;
while(res.length() < ZIP) res += '0';
reverse(res.begin(), res.end());
return res;
}
inline void zip() {
rep(i, 0, MAXN - 1) a[i] = 0;
int len = num.length();
if(len % ZIP) {
int END = (len / ZIP + 1) * ZIP - len;
rep(i, 1, END) num = '0' + num;
}
len = num.length();
int i = len, j = 0;
do {
if(i >= ZIP) {
a[j] = toint(num.substr(i - ZIP, ZIP));
i -= ZIP;
}
else {
int x = i;
i = 0;
a[j] = toint(num.substr(i, x));
break;
}
++ j;
}while(i >= 0);
cnt = j - 1;
}
//数字字符串比大小,a大返回1,b大返回2,相等返回0
inline int cmp(string a, string b) {
if(a == b) return 0;
if(a.length() == b.length()) {
if(a > b) return 1;
if(a < b) return 2;
}
if(a.length() > b.length()) return 1;
if(a.length() < b.length()) return 2;
}
string sub(string x, string y) {
if(y == "0") return x;
string res;
int xa[MAXN], ya[MAXN], len1 = x.length(), len2 = y.length();
int END = max(len1, len2);
reverse(x.begin(), x.end());
reverse(y.begin(), y.end());
rep(i, 0, MAXN - 1) xa[i] = 0, ya[i] = 0;
rep(i, 0, len1 - 1) xa[i] = x[i] - '0';
rep(i, 0, len2 - 1) ya[i] = y[i] - '0';
rep(i, 0, END) xa[i] -= ya[i];
rep(i, 0, END)
if(xa[i] < 0) xa[i] += 10, xa[i + 1] --;
rep(i, 0, END) res += xa[i] + '0';
int i = res.length() - 1;
while(res[i] == '0') -- i;
res.erase(i + 1);
reverse(res.begin(), res.end());
return res;
}
//低精乘高精
string mul(int x, string y) {
if(x == 0 || y == "0") return "0";
if(x == 1) return y;
if(y == "1") {
string res;
while(x) res += x % 10, x /= 10;
reverse(res.begin(), res.end());
return res;
}
string res; //商
reverse(y.begin(), y.end());
int len2 = y.length(), t[MAXN];
rep(i, 0, MAXN - 1) t[i] = 0;
rep(i, 0, MAXN - 1) {
if(i <= len2 - 1) t[i] += x * (y[i] - '0');
t[i + 1] += t[i] / 10;
t[i] %= 10;
}
int END = MAXN - 1;
while(!t[END]) -- END;
for(int i = END; i >= 0; -- i) res += t[i] + '0';
return res;
}
//试商函数,x被除数y除数,假设x > y
inline int TRY(string x, string y) {
int len1 = x.length(), len2 = y.length(), mid, l = 0, r = 10;
const int MAXT = 1005;
int t[MAXT], ans;
while(l <= r) {
mid = (l + r) >> 1;
//低精乘高精,y * mid
string quo; //商
quo = mul(mid, y);
//判断当前商是否小于被除数x
if(quo == x) { tmp = quo, ans = mid; return mid; }
else if(cmp(x, quo) == 2) r = mid - 1;
else if(cmp(x, quo) == 1) l = mid + 1, tmp = quo, ans = mid;
}
return ans;
}
bool operator < (const BIGN &t) {
if(num.length() == t.num.length()) return num < t.num;
if(num.length() > t.num.length()) return 0;
if(num.length() < t.num.length()) return 1;
}
bool operator > (const BIGN &t) {
if(num.length() == t.num.length()) return num > t.num;
if(num.length() > t.num.length()) return 1;
if(num.length() < t.num.length()) return 0;
}
BIGN operator + (const BIGN &t) {
BIGN x = *this, y = t;
if(x.num == "0") return y;
if(y.num == "0") return x;
x.zip(), y.zip();
POW = pow(10, ZIP);
int END = max(x.cnt, y.cnt) + 2;
rep(i, 0, END) x.a[i] += y.a[i];
rep(i, 0, END) x.a[i + 1] += x.a[i] / POW, x.a[i] %= POW;
x.num = "";
for(int i = END; i >= 0; -- i) x.num += tostr(x.a[i]);
int i = 0;
while(x.num[i] == '0') ++ i;
x.num.erase(0, i);
return x;
}
BIGN operator - (const BIGN &t) {
BIGN x = *this, y = t;
if(y.num == "0") return x;
if(x.num == y.num) { x.num = "0"; return x; }
int f = 0;
if(cmp(x.num, y.num) == 2) f = 1, swap(x, y);
x.zip(), y.zip();
POW = pow(10, ZIP);
int END = max(x.cnt, y.cnt) + 2;
rep(i, 0, END) x.a[i] -= y.a[i];
rep(i, 0, END - 2)
if(x.a[i] < 0) x.a[i] += POW, x.a[i + 1] --;
x.num = "";
for(int i = END; i >= 0; -- i) x.num += tostr(x.a[i]);
int i = 0;
while(x.num[i] == '0') ++ i;
x.num.erase(0, i);
if(f == 1) x.num = '-' + x.num;
return x;
}
BIGN operator * (const BIGN &t) {
BIGN x = *this, y = t;
if(x.num == "0" || y.num == "0") return x;
if(x.num == "1") return y;
if(y.num == "1") return x;
x.zip(), y.zip();
POW = pow(10, ZIP);
int c[MAXN << 1];
rep(i, 0, x.cnt) {
rep(j, 0, y.cnt) c[i + j] += x.a[i] * y.a[j], c[i + j + 1] += c[i + j] / POW, c[i + j] %= POW;
}
x.num = "";
int END = x.cnt + y.cnt;
for(int i = END + 2; i >= 0; -- i) x.num += tostr(c[i]);
int i = 0;
while(x.num[i] == '0') ++ i;
x.num.erase(0, i);
return x;
}
BIGN operator / (const BIGN &t) {
BIGN x = *this, y = t;
if(x.num == "0") return x;
if(y.num == "1") return x;
if(x.num == y.num) { x.num = "1"; return x; }
if(cmp(y.num, x.num) == 1) { x.rem = x.num, x.num = "0"; return x; }
string res, bchu;
int cur = y.num.length() - 1; //cur存右边的
int len1 = x.num.length(), len2 = y.num.length();
bchu = x.num.substr(0, len2);
int f = 0;
while(cur <= len1 - 2) {
if(f) bchu += x.num[++ cur];
f = 1;
int shang = TRY(bchu, y.num);
string xx = sub(bchu, tmp);
if(xx != "0") bchu = xx;
else bchu = "";
x.rem = xx;
res += shang + '0';
}
int i = 0;
while(res[i] == '0') ++ i;
res.erase(0, i);
x.num = res;
return x;
//7763912854 31
}
} a, b, c;
int main() {
ios::sync_with_stdio(false);
//freopen("data.in", "r", stdin); freopen("data.out", "w", stdout);
a.READ();
b.READ();
c = a + b;
c.WRITE();
cout << endl;
c = a - b;
c.WRITE();
cout << endl;
c = a * b;
c.WRITE();
cout << endl;
c = a / b;
c.WRITE();
cout << endl;
cout << c.rem << endl;
return 0;
}