Từ CHVOJ: CHV Online Judge, NHÓM DỰ NGUỒN ĐTQG 25-26
Thông tin
include <bits/stdc++.h>
using namespace std;
int cmp(const string &a, const string &b) { if (a.size() != b.size()) return a.size() < b.size() ? -1 : 1; if (a == b) return 0; return a < b ? -1 : 1; }
string mul(const string &a, const string &b) { int n = a.size(), m = b.size(); vector<int> res(n + m, 0); for (int i = n - 1; i >= 0; --i) for (int j = m - 1; j >= 0; --j) res[i + j + 1] += (a[i] - '0') * (b[j] - '0'); for (int i = n + m - 1; i > 0; --i) if (res[i] >= 10) { res[i - 1] += res[i] / 10; res[i] %= 10; } string s; int i = 0; while (i < n + m && res[i] == 0) ++i; for (; i < n + m; ++i) s.push_back(res[i] + '0'); return s.empty() ? "0" : s; }
string add1(string s) { int i = s.size() - 1; while (i >= 0 && s[i] == '9') s[i--] = '0'; if (i < 0) s = '1' + s; else s[i]++; return s; }
string sub1(string s) { int i = s.size() - 1; while (i >= 0 && s[i] == '0') s[i--] = '9'; if (i >= 0) s[i]--; if (s[0] == '0' && s.size() > 1) s.erase(0, s.findfirstnot_of('0')); return s; }
string div2(const string &a) { string res; int carry = 0; for (char c : a) { int cur = carry * 10 + (c - '0'); res.pushback(cur / 2 + '0'); carry = cur % 2; } res.erase(0, res.findfirstnotof('0')); return res.empty() ? "0" : res; }
string add(const string &a, const string &b) { string A = a, B = b; if (A.size() < B.size()) swap(A, B); while (B.size() < A.size()) B = '0' + B; int carry = 0; for (int i = A.size() - 1; i >= 0; --i) { int sum = (A[i] - '0') + (B[i] - '0') + carry; A[i] = sum % 10 + '0'; carry = sum / 10; } if (carry) A = '1' + A; return A; }
int main() { ios::syncwithstdio(false); cin.tie(nullptr); string N; cin >> N; string lo = "0", hi = N, mid, sq; while (cmp(lo, hi) <= 0) { mid = div2(add(lo, hi)); sq = mul(mid, mid); int c = cmp(sq, N); if (c == 0) { cout << mid; return 0; } else if (c < 0) lo = add1(mid); else hi = sub1(mid); } cout << "no"; }