关于UB
查看原帖
关于UB
317650
lao_lihiOI楼主2021/2/16 19:35

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;
}
2021/2/16 19:35
加载中...