#include <functional> #include <queue> #include <vector> #include <iostream> using namespace std; typedef unsigned long long ull; typedef long long ll; inline ull add(ull u, ull v) { ull uv; if (__builtin_uaddll_overflow(u,v,&uv)) { cerr << "# add overflow" << endl; exit(1); } else { return uv; } } inline ull mul(ull u, ull v) { ull uv; if (__builtin_umulll_overflow(u,v,&uv)) { cerr << "# mul overflow" << endl; exit(1); } else { return uv; } } class RepDigit { public: RepDigit(ull base) { this->Base = base; this->Value = this->Repunit = add(mul(base,base), add(base,1)); this->Digit = 1; } ull Base; ull Repunit; ull Digit; ull Value; void Forward() { this->Digit++; if (this->Digit==this->Base) { this->Digit = 1; this->Value = this->Repunit = add(mul(this->Repunit, this->Base), 1); } else { this->Value = add(this->Value, this->Repunit); } } }; struct RepDigitCompare { bool operator()(const RepDigit *lhs, const RepDigit *rhs) { if (lhs->Value > rhs->Value) { return true; } else if (lhs->Value==rhs->Value && lhs->Base > rhs->Base) { return true; } else { return false; } } }; priority_queue<RepDigit*, vector<RepDigit*>, RepDigitCompare> repdigits; RepDigit *nxt = new RepDigit(2); static long pop() { while (repdigits.empty() || nxt->Value <= repdigits.top()->Value) { repdigits.push(nxt); nxt = new RepDigit(nxt->Base+1); } RepDigit *top = repdigits.top(); repdigits.pop(); ull value = top->Value; top->Forward(); repdigits.push(top); return value; } // 563 75059993789508 int main() { cerr << "#skipping" << endl; ull after = 75059993789501; while (nxt->Value<after) { while (nxt->Value<after) { nxt->Forward(); } repdigits.push(nxt); nxt = new RepDigit(nxt->Base+1); } cerr << "#skipped " << nxt->Base << endl; int n = 563-1; ull value = 0; int count = 0; while (true) { ull other = pop(); if (value==other) { count++; if (count==3) { n++; cout << n << " " << value << endl; } } else { value = other; count = 1; } } return 0; }