题解：P17181 [ICPC 2017 Hong Kong R] Fermat's Optimization Problem
Analysis
直接枚举
由于每一次要么
Code
由于高精度太过珂爱，先给省略高精度部分的代码。
#include"bits/stdc++.h"
using namespace std;
int t, n;
struct BigInt {
//此处省略 100 多行
};
BigInt z;
signed main() {
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
cin >> t;
while (t--) {
cin >> n >> z;
BigInt x = 1, y = z - 1;
BigInt xn = x ^ n, yn = y ^ n, zn = z ^ n;// ^ 为幂运算
BigInt ans = abs(xn + yn - zn);
BigInt ansx = 1, ansy = z - 1;
while (x < y) {
BigInt cur = xn + yn - zn;
if (abs(cur) < ans) {
ansx = x;
ansy = y;
ans = abs(cur);
}
if (cur < 0)
x++, xn = x ^ n;
else if (cur > 0)
y--, yn = y ^ n;
else
break;
}
cout << ansx << ' ' << ansy << ' ' << ans << '\n';
}
return 0;
}:::info[高精度]
struct BigInt {
vector<int> digits;
bool is_neg = false;
BigInt() : digits(1, 0), is_neg(false) {}
BigInt(long long v) {
if (v < 0) {
is_neg = true;
v = -v;
} else {
is_neg = false;
}
if (v == 0) digits.push_back(0);
while (v > 0) {
digits.push_back(v % 10);
v /= 10;
}
}
BigInt(const string& s) {
is_neg = false;
if (s.empty()) {
digits.push_back(0);
return;
}
int start = 0;
if (s[0] == '-') {
is_neg = true;
start = 1;
} else if (s[0] == '+') {
start = 1;
}
for (int i = s.length() - 1; i >= start; i--) {
digits.push_back(s[i] - '0');
}
trim();
}
void trim() {
while (digits.size() > 1 && digits.back() == 0) {
digits.pop_back();
}
if (digits.size() == 1 && digits[0] == 0) {
is_neg = false;
}
}
BigInt abs() const {
BigInt res = *this;
res.is_neg = false;
return res;
}
friend BigInt abs(const BigInt& a) {
return a.abs();
}
BigInt operator-() const {
if (digits.size() == 1 && digits[0] == 0) return *this;
BigInt res = *this;
res.is_neg = !res.is_neg;
return res;
}
static bool abs_less(const BigInt& a, const BigInt& b) {
if (a.digits.size() != b.digits.size()) {
return a.digits.size() < b.digits.size();
}
for (int i = (int)a.digits.size() - 1; i >= 0; i--) {
if (a.digits[i] != b.digits[i]) {
return a.digits[i] < b.digits[i];
}
}
return false;
}
bool operator<(const BigInt& b) const {
if (is_neg != b.is_neg) return is_neg;
if (is_neg) return abs_less(b, *this);
return abs_less(*this, b);
}
bool operator>(const BigInt& b) const { return b < *this; }
bool operator<=(const BigInt& b) const { return !(*this > b); }
bool operator>=(const BigInt& b) const { return !(*this < b); }
bool operator==(const BigInt& b) const { return is_neg == b.is_neg && digits == b.digits; }
bool operator!=(const BigInt& b) const { return !(*this == b); }
static BigInt add_unsigned(const BigInt& a, const BigInt& b) {
BigInt res;
res.digits.clear();
int carry = 0;
for (size_t i = 0; i < max(a.digits.size(), b.digits.size()) || carry; ++i) {
if (i < a.digits.size()) carry += a.digits[i];
if (i < b.digits.size()) carry += b.digits[i];
res.digits.push_back(carry % 10);
carry /= 10;
}
return res;
}
static BigInt sub_unsigned(const BigInt& a, const BigInt& b) {
BigInt res;
res.digits.clear();
int borrow = 0;
for (size_t i = 0; i < a.digits.size(); ++i) {
int diff = a.digits[i] - borrow - (i < b.digits.size() ? b.digits[i] : 0);
if (diff < 0) {
diff += 10;
borrow = 1;
} else {
borrow = 0;
}
res.digits.push_back(diff);
}
res.trim();
return res;
}
BigInt operator+(const BigInt& b) const {
if (is_neg == b.is_neg) {
BigInt res = add_unsigned(*this, b);
res.is_neg = is_neg;
res.trim();
return res;
}
if (abs_less(*this, b)) {
BigInt res = sub_unsigned(b, *this);
res.is_neg = b.is_neg;
res.trim();
return res;
} else {
BigInt res = sub_unsigned(*this, b);
res.is_neg = is_neg;
res.trim();
return res;
}
}
BigInt operator-(const BigInt& b) const {
return *this + (-b);
}
BigInt operator*(const BigInt& b) const {
BigInt res;
res.digits.assign(digits.size() + b.digits.size(), 0);
for (size_t i = 0; i < digits.size(); ++i) {
long long carry = 0;
for (size_t j = 0; j < b.digits.size(); ++j) {
long long cur = res.digits[i + j] + (long long)digits[i] * b.digits[j] + carry;
res.digits[i + j] = cur % 10;
carry = cur / 10;
}
if (carry > 0) {
res.digits[i + b.digits.size()] += carry;
}
}
res.is_neg = is_neg ^ b.is_neg;
res.trim();
return res;
}
BigInt operator/(const int& b) const {
BigInt res;
res.digits.clear();
long long current = 0;
int abs_b = std::abs(b);
for (int i = digits.size() - 1; i >= 0; i--) {
current = current * 10 + digits[i];
res.digits.push_back(current / abs_b);
current %= abs_b;
}
reverse(res.digits.begin(), res.digits.end());
res.is_neg = is_neg ^ (b < 0);
res.trim();
return res;
}
long long operator%(const int& b) const {
long long current = 0;
int abs_b = std::abs(b);
for (int i = digits.size() - 1; i >= 0; i--) {
current = (current * 10 + digits[i]) % abs_b;
}
return is_neg ? -current : current;
}
BigInt pow(long long n) const {
BigInt res(1);
BigInt base = *this;
while (n > 0) {
if (n % 2 == 1) res = res * base;
base = base * base;
n /= 2;
}
return res;
}
BigInt operator^(const long long& n) const { return this->pow(n); }
BigInt& operator+=(const BigInt& b) { return *this = *this + b; }
BigInt& operator-=(const BigInt& b) { return *this = *this - b; }
BigInt& operator*=(const BigInt& b) { return *this = *this * b; }
BigInt& operator/=(const int& b) { return *this = *this / b; }
BigInt& operator%=(const int& b) { return *this = BigInt(*this % b); }
BigInt& operator^=(const long long& n) { return *this = *this ^ n; }
BigInt& operator++() { return *this += 1; }
BigInt operator++(signed) { BigInt temp = *this; *this += 1; return temp; }
BigInt& operator--() { return *this -= 1; }
BigInt operator--(signed) { BigInt temp = *this; *this -= 1; return temp; }
friend istream& operator>>(istream& in, BigInt& a) {
string s;
in >> s;
a = BigInt(s);
return in;
}
friend ostream& operator<<(ostream& out, const BigInt& a) {
if (a.is_neg) out << '-';
for (int i = a.digits.size() - 1; i >= 0; i--) {
out << a.digits[i];
}
return out;
}
};