#include #include #include #include #include using namespace std; typedef unsigned long long uint64; typedef vector ivector; #define BASE 1000000000 class BigInt { public: BigInt() {} BigInt(uint64 value); BigInt(const BigInt &value) : _data(value._data) {} BigInt &operator=(const BigInt &v); BigInt operator*(const BigInt &v) const; BigInt &operator*=(const BigInt &v); BigInt &operator*=(int v); BigInt &operator+=(const BigInt &v); BigInt operator+(const BigInt &v) const {BigInt value(*this); return value+=v;} BigInt &operator<<=(int l); BigInt operator<<(int l) const {BigInt value(*this); return value<<=l;} bool operator<(const BigInt &v) const {return cmp(v) < 0;} bool operator<=(const BigInt &v) const {return cmp(v) <= 0;} bool operator>(const BigInt &v) const {return cmp(v) > 0;} bool operator>=(const BigInt &v) const {return cmp(v) >= 0;} bool operator==(const BigInt &v) const {return cmp(v) == 0;} bool operator!=(const BigInt &v) const {return cmp(v) != 0;} int cmp(const BigInt &v) const; bool endsWith(const BigInt &v) const; string to_s() const; private: ivector _data; BigInt &mul_add_shift(const BigInt &v, unsigned int m, int shift=0); }; BigInt::BigInt(uint64 value) { while (value >= BASE) { _data.push_back(value%BASE); value /= BASE; } _data.push_back(value); } BigInt &BigInt::operator=(const BigInt &v) { _data = v._data; return *this; } BigInt &BigInt::operator*=(int v) { uint64 pass = 0; ivector::iterator it, end = _data.end(); for (it = _data.begin(); it != end; it++) { uint64 res = *it * v + pass; pass = 0; if (res >= BASE) { pass = res / BASE; res %= BASE; } *it = res; } if (pass) _data.push_back(pass); return *this; } BigInt & BigInt::mul_add_shift(const BigInt &v, unsigned int m, int shift) { // optimization; without this the program runs 80 secs against 32 to calculate 10000 numbers uint64 pass = 0; int n = v._data.size() + shift; if (_data.size() < n) _data.resize(n); ivector::iterator it = _data.begin() + shift, end = _data.end(); ivector::const_iterator v_it = v._data.begin(); for (; it!=end; it++, v_it++) { uint64 res = *v_it * m + *it + pass; pass = 0; if (res >= BASE) { pass = res / BASE; res %= BASE; } *it = res; } if (pass) _data.push_back(pass); return *this; } BigInt &BigInt::operator*=(const BigInt &v) { *this = *this * v; return *this; } BigInt BigInt::operator*(const BigInt &v) const { BigInt res; ivector::const_iterator it, end = v._data.end(); int i=0; for (it = v._data.begin(); it != end; it++, i++) { res.mul_add_shift(*this, *it, i); } return res; } BigInt &BigInt::operator+=(const BigInt &v) { uint64 pass = 0; if (_data.size() < v._data.size()) _data.resize(v._data.size()); ivector::const_iterator v_it = v._data.begin(); for (ivector::iterator it = _data.begin(); it != _data.end(); it++, v_it++) { uint64 res = *it + *v_it + pass; pass = 0; if (res >= BASE) { pass = res/BASE; res %= BASE; } *it = res; } if (pass) _data.push_back(pass); return *this; } BigInt &BigInt::operator<<=(int l) { _data.insert(_data.begin(), l, 0); return *this; } int BigInt::cmp(const BigInt& v) const { // if size of this is larger then v, return this-v if (_data.size() != v._data.size()) return _data.size() - v._data.size(); // compare this with v number by number, starting from end ivector::const_reverse_iterator it, vit, end = _data.rend(); for (it = _data.rbegin(), vit = v._data.rbegin(); it != end; it++, vit++) { if (*it != *vit) return *it - *vit; } // this equal to v return 0; } bool BigInt::endsWith(const BigInt& v) const { ivector::const_iterator it = _data.begin(), v_it = v._data.begin(), v_end = v._data.end(); v_end--; for (; v_it != v_end; it++, v_it++) if (*it != *v_it) return false; uint64 a = *it, b = *v_it; while (b) { if (a%10 != b%10) return false; a/=10; b/=10; } return true; } string BigInt::to_s() const { ostringstream ss; int n = _data.size()-1; ivector::const_reverse_iterator rit, rbegin = _data.rbegin(), rend = _data.rend(); for (rit = rbegin; rit != rend; rit++) ss << setw(rit==rbegin?0:9) << setfill(rit==rbegin?' ':'0') << *rit; return ss.str(); } void out(const BigInt &v) { static int l = 1; cout << l++ << ": " << v.to_s() << endl; } void findAutomorphic(int n) { int count = 3; BigInt am[2] = {BigInt(5), BigInt(6)}; out(BigInt(1)); out(am[0]); out(am[1]); BigInt p(10); while (count < n) { BigInt var[2] = {am[0], am[1]}; bool new_am[2] = {false, false}; for (int j=0; j<2; j++) { if (count >= n) break; for (int k=0; k<9; k++) { var[j] += p; BigInt square = var[j]*var[j]; if (square.endsWith(var[j])) { new_am[j] = true; am[j] = var[j]; count++; break; } } } if (new_am[0] && new_am[1]) { if (am[0] < am[1]) { out(am[0]); out(am[1]); } else { out(am[1]); out(am[0]); } } else for (int i=0; i<2; i++) if (new_am[i]) out(am[i]); p *= 10; } } int main(int argc, char **argv) { int n; cout << "Count of automorphic numbers: "; cin >> n; findAutomorphic(n); return 0; }

automorphic_big