60(没过的TLE)
  • 板块P2005 A/B Problem II
  • 楼主cgxd
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/6/9 18:38
  • 上次更新2024/6/9 18:44:17
查看原帖
60(没过的TLE)
1272259
cgxd楼主2024/6/9 18:38
#include<bits/stdc++.h>
using namespace std;
map<string, map<string, string>> m;
bool operator<(pair<string, string> a, pair<string, string> b){
	return a.first < b.first;
}string operator+(string s1, string s2){
	if(s1.size() < s2.size())
		swap(s1, s2);
	if(s2 == "0")
		return s1;
	reverse(s1.begin(), s1.end());
	reverse(s2.begin(), s2.end());
	s2.resize(s1.size(), '0');
	s1.push_back('0');
	for(size_t i = 0; i < s2.size(); ++i){
		s1[i] += s2[i] - '0';
		if(s1[i] > '9'){
			s1[i] -= 10;
			++s1[i + 1];
		}
	}while(s1.back() == '0')
		s1.pop_back();
	if(s1.empty())
		return "0";
	reverse(s1.begin(), s1.end());
	return s1;
}string operator*(string s1, string s2){
	if(s1 == "0" or s2 == "0")
		return "0";
	if(s2 == "10"){
		s1.push_back('0');
		return s1;
	}if(m.count(s1) and m[s1].count(s2))
		return m[s1][s2];
	if(s1.size() == 1 and s2.size() == 1){
		m[s1][s2] = to_string((s1[0] - '0') * (s2[0] - '0'));
		return m[s1][s2];
	}string ans("0");
	for(char c: s1){
		string s3(1, c);
		ans = ans * "10" + s2 * s3;
	}m[s1][s2] = ans;
	return ans;
}string devide(string s){
	string s1;
	if(s == "0" or s == "1")
		return 0;
	for(int i = 0; i < s.size() - 1; i++){
		s1.push_back((s[i] - 48) / 2 + 48);
		s[i + 1] += (s[i] - 48) % 2 * 10;
	}s1.push_back((s.back() - 48) / 2 + 48);
	reverse(s1.begin(), s1.end());
	s1.push_back(48);
	for(int i = 0; i < s1.size() - 1; i++){
		while(s1[i] > 57){
			s1[i] -= 10;
			s1[i + 1]++;
		}
	}while(s1.back() == 48)
		s1.pop_back();
	reverse(s1.begin(), s1.end());
	reverse(s.begin(), s.end());
	if(s1.empty())
		return "0";
	return s1;
}bool operator>(string s1, string s2){
	if(s1.size() != s2.size())
		return s1.size() > s2.size();
	return !(s1 < s2 or s1 == s2);
}int main(){
	string s1, s2;
	cin >> s1 >> s2;
	string left(s1), right(s1);
	left.resize(left.size() - s2.size());
	right.resize(right.size() - s2.size() + 1);
	if(s2 > s1){
		cout << 0;
		return 0;
	}if(left.empty())
		left = "0";
	if(right.empty())
		right = "0";
	while(right > left){
		string mid = devide(left + right);
		string ans = mid * s2;
		if(s1 == ans or ans + s2 > s1 and s1 > ans){
			cout << mid;
			return 0;
		}else if(ans > s1)
			right = mid;
		else 
			left = mid;
	}cout << (right * s2 == s1? right: left);
	return 0;
}
2024/6/9 18:38
加载中...