ba35b3a9cf 2011-06-25 kinaba: #include <iostream> ba35b3a9cf 2011-06-25 kinaba: #include <sstream> ba35b3a9cf 2011-06-25 kinaba: #include <iomanip> ba35b3a9cf 2011-06-25 kinaba: #include <vector> ba35b3a9cf 2011-06-25 kinaba: #include <string> ba35b3a9cf 2011-06-25 kinaba: #include <map> ba35b3a9cf 2011-06-25 kinaba: #include <set> ba35b3a9cf 2011-06-25 kinaba: #include <algorithm> ba35b3a9cf 2011-06-25 kinaba: #include <numeric> ba35b3a9cf 2011-06-25 kinaba: #include <iterator> ba35b3a9cf 2011-06-25 kinaba: #include <functional> ba35b3a9cf 2011-06-25 kinaba: #include <complex> ba35b3a9cf 2011-06-25 kinaba: #include <queue> ba35b3a9cf 2011-06-25 kinaba: #include <stack> ba35b3a9cf 2011-06-25 kinaba: #include <cmath> ba35b3a9cf 2011-06-25 kinaba: #include <cassert> ba35b3a9cf 2011-06-25 kinaba: #include <cstring> ba35b3a9cf 2011-06-25 kinaba: using namespace std; ba35b3a9cf 2011-06-25 kinaba: typedef long long LL; ba35b3a9cf 2011-06-25 kinaba: typedef complex<double> CMP; ba35b3a9cf 2011-06-25 kinaba: ba35b3a9cf 2011-06-25 kinaba: class TheLuckyBasesDivOne { public: ba35b3a9cf 2011-06-25 kinaba: set<LL> all; ba35b3a9cf 2011-06-25 kinaba: void computeAll() ba35b3a9cf 2011-06-25 kinaba: { ba35b3a9cf 2011-06-25 kinaba: for(int len=1; len<=15; ++len) ba35b3a9cf 2011-06-25 kinaba: { ba35b3a9cf 2011-06-25 kinaba: for(int pat=0; pat<(1<<len); ++pat) ba35b3a9cf 2011-06-25 kinaba: { ba35b3a9cf 2011-06-25 kinaba: LL val = 0; ba35b3a9cf 2011-06-25 kinaba: for(int i=0; i<len; ++i) ba35b3a9cf 2011-06-25 kinaba: val = val*10 + ((pat&(1<<i)) ? 7 : 4); ba35b3a9cf 2011-06-25 kinaba: all.insert(val); ba35b3a9cf 2011-06-25 kinaba: } ba35b3a9cf 2011-06-25 kinaba: } ba35b3a9cf 2011-06-25 kinaba: } ba35b3a9cf 2011-06-25 kinaba: ba35b3a9cf 2011-06-25 kinaba: long long find(long long n) ba35b3a9cf 2011-06-25 kinaba: { ba35b3a9cf 2011-06-25 kinaba: computeAll(); ba35b3a9cf 2011-06-25 kinaba: if( all.count(n) ) // if itself is lucky, then inf. ba35b3a9cf 2011-06-25 kinaba: return -1; ba35b3a9cf 2011-06-25 kinaba: ba35b3a9cf 2011-06-25 kinaba: LL cnt = 0; ba35b3a9cf 2011-06-25 kinaba: // 3 or more B-its ba35b3a9cf 2011-06-25 kinaba: for(LL B=2; B*B*B<=n; ++B) ba35b3a9cf 2011-06-25 kinaba: if( isLuckyBase(n, B) ) ba35b3a9cf 2011-06-25 kinaba: ++cnt; ba35b3a9cf 2011-06-25 kinaba: // 2 B-its ba35b3a9cf 2011-06-25 kinaba: for(set<LL>::iterator it=all.begin(); it!=all.end(); ++it) ba35b3a9cf 2011-06-25 kinaba: { ba35b3a9cf 2011-06-25 kinaba: LL r = n-*it; ba35b3a9cf 2011-06-25 kinaba: for(LL B=*it+1; B<=n/B && B*B<n; ++B) { ba35b3a9cf 2011-06-25 kinaba: if( r%B==0 && n/B<B && all.count(n/B) ) ba35b3a9cf 2011-06-25 kinaba: ++cnt; ba35b3a9cf 2011-06-25 kinaba: } ba35b3a9cf 2011-06-25 kinaba: } ba35b3a9cf 2011-06-25 kinaba: return cnt; ba35b3a9cf 2011-06-25 kinaba: } ba35b3a9cf 2011-06-25 kinaba: ba35b3a9cf 2011-06-25 kinaba: bool isLuckyBase(LL n, LL B) ba35b3a9cf 2011-06-25 kinaba: { ba35b3a9cf 2011-06-25 kinaba: for(;n; n/=B) ba35b3a9cf 2011-06-25 kinaba: if( !all.count(n%B) ) ba35b3a9cf 2011-06-25 kinaba: return false; ba35b3a9cf 2011-06-25 kinaba: return true; ba35b3a9cf 2011-06-25 kinaba: } ba35b3a9cf 2011-06-25 kinaba: }; ba35b3a9cf 2011-06-25 kinaba: ba35b3a9cf 2011-06-25 kinaba: // BEGIN CUT HERE ba35b3a9cf 2011-06-25 kinaba: #include <ctime> ba35b3a9cf 2011-06-25 kinaba: double start_time; string timer() ba35b3a9cf 2011-06-25 kinaba: { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } ba35b3a9cf 2011-06-25 kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) ba35b3a9cf 2011-06-25 kinaba: { os << "{ "; ba35b3a9cf 2011-06-25 kinaba: for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) ba35b3a9cf 2011-06-25 kinaba: os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } ba35b3a9cf 2011-06-25 kinaba: void verify_case(const long long& Expected, const long long& Received) { ba35b3a9cf 2011-06-25 kinaba: bool ok = (Expected == Received); ba35b3a9cf 2011-06-25 kinaba: if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; ba35b3a9cf 2011-06-25 kinaba: cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } ba35b3a9cf 2011-06-25 kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); ba35b3a9cf 2011-06-25 kinaba: #define END verify_case(_, TheLuckyBasesDivOne().find(n));} ba35b3a9cf 2011-06-25 kinaba: int main(){ ba35b3a9cf 2011-06-25 kinaba: ba35b3a9cf 2011-06-25 kinaba: CASE(0) ba35b3a9cf 2011-06-25 kinaba: long long n = 255LL; ba35b3a9cf 2011-06-25 kinaba: long long _ = 2LL; ba35b3a9cf 2011-06-25 kinaba: END ba35b3a9cf 2011-06-25 kinaba: CASE(1) ba35b3a9cf 2011-06-25 kinaba: long long n = 474LL; ba35b3a9cf 2011-06-25 kinaba: long long _ = -1LL; ba35b3a9cf 2011-06-25 kinaba: END ba35b3a9cf 2011-06-25 kinaba: CASE(2) ba35b3a9cf 2011-06-25 kinaba: long long n = 13LL; ba35b3a9cf 2011-06-25 kinaba: long long _ = 0LL; ba35b3a9cf 2011-06-25 kinaba: END ba35b3a9cf 2011-06-25 kinaba: CASE(3) ba35b3a9cf 2011-06-25 kinaba: long long n = 4748LL; ba35b3a9cf 2011-06-25 kinaba: long long _ = 5LL; ba35b3a9cf 2011-06-25 kinaba: END ba35b3a9cf 2011-06-25 kinaba: CASE(4) ba35b3a9cf 2011-06-25 kinaba: long long n = 1LL; ba35b3a9cf 2011-06-25 kinaba: long long _ = 0LL; ba35b3a9cf 2011-06-25 kinaba: END ba35b3a9cf 2011-06-25 kinaba: CASE(5) ba35b3a9cf 2011-06-25 kinaba: long long n = 10000000000000000LL; ba35b3a9cf 2011-06-25 kinaba: long long _ = -1LL; ba35b3a9cf 2011-06-25 kinaba: END ba35b3a9cf 2011-06-25 kinaba: ba35b3a9cf 2011-06-25 kinaba: } ba35b3a9cf 2011-06-25 kinaba: // END CUT HERE