虽然这道题使用 double 类型就可以过,但我由于担心精度问题还是写了高精度。
实际上,由于一个数被乘方之后很小的差别对应的结果差别非常大,所以 double 应该确实可以。
#include <iostream> #include <cstring> #include <string> #include <cstdio> using namespace std; const int bitlen = sizeof(long); const int bitmax = 10000; #define maxof(a,b) (a > b ? a : b) int a; string b; /* Class Number * Represents a big number. */ template<int T> class number { public: /* init a new number by a input of integer. */ number(const long i) { init(); if (i < bitmax) { bit[0] = 1; bit[T] = i; return; } long l = 0, j = i, m; while ((m = j / bitmax, j) != 0) { bit[T - l++] = j - m * bitmax; j = m; } bit[0] = l; } /* the real size of bit[] */ long size() const { return bit[0]; } void show() const { if (bit[0] == 0) { cout << "0"; return; } for (int i = 0; i < bit[0]; ++i) { cout << bit[T - bit[0] + i + 1]; } cout << "(" << bit[0] << ")" << endl; } string showToString() const { if (bit[0] == 0) { return string("0"); } string s; char ct[5]; for (int i = 0; i < bit[0]; ++i) { sprintf(ct, "%d", bit[T - bit[0] + i + 1]); int p = 4 - strlen(ct); if (p > 0 && i != 0) for (int f = 0; f < p; ++f) s.append ("0"); s.append(ct); } return s; } number<T> operator+(const number<T> &num2) const { if (num2.size() == 0) { return *this; } int len = maxof(this->size(), num2.size()), jw = 0; number<T> sum(0); for (int a = 0; a < len; ++a) { sum.bit[T - a] = this->bit[T - a] + num2.bit[T - a] + jw; jw = 0; if (sum.bit[T - a] >= bitmax) { sum.bit[T - a] %= bitmax; jw = 1; } } if (jw == 1) len++; sum.bit[0] = len; return sum; } number<T> operator<<(const int i) const { if (i != 1) throw exception(); number<T> tmp(*this); for (int i = tmp.size (); i > 0; --i) tmp.bit[T - i] = tmp.bit[T - i + 1]; tmp.bit[T] = 0; tmp.bit[0]++; return tmp; } number<T> operator*(const number<T> &num2) const { if (this->size() == 0 || num2.size() == 0) { return number<T>(0); // 0 } if (this->size() == 1 && num2.size() == 1) { return number<T>(this->bit[T] * num2.bit[T]); } number<T> sum(0); for (int a = 0; a < this->size(); ++a) { for (int b = 0; b < num2.size(); ++b) { int cj = this->bit[T - a] * num2.bit[T - b]; number<T> tmp(cj); for (int c = 0; c < a + b; ++c) { tmp = tmp << 1; } sum = sum + tmp; } } return sum; } long bit[T + 1]; private: void init() { memset(bit, 0, sizeof(bit)); } }; typedef number<100> bignum; bignum power(int i, int p) { bignum tmp(i), tmp2(i); for (int i = 0; i < p - 1; ++i) tmp = tmp * tmp2; return tmp; } void check(int l, int r) { if (l == r) { cout << l << endl; return; } int m = (l + r) / 2; bignum tmp = power(m, a); string ss = tmp.showToString(); if (b == ss) { cout << m << endl; return; } else { if (ss.size() > b.size() || (ss.size() == b.size() && ss > b)) { check (l, m - 1); } else { check (m + 1, r); } } } int main () { while (cin >> a >> b) { check(1, 1000000000); } return 0; } |