744af0f22d 2014-07-26 kinaba: #include <iostream> 744af0f22d 2014-07-26 kinaba: #include <sstream> 744af0f22d 2014-07-26 kinaba: #include <iomanip> 744af0f22d 2014-07-26 kinaba: #include <vector> 744af0f22d 2014-07-26 kinaba: #include <string> 744af0f22d 2014-07-26 kinaba: #include <map> 744af0f22d 2014-07-26 kinaba: #include <set> 744af0f22d 2014-07-26 kinaba: #include <algorithm> 744af0f22d 2014-07-26 kinaba: #include <numeric> 744af0f22d 2014-07-26 kinaba: #include <iterator> 744af0f22d 2014-07-26 kinaba: #include <functional> 744af0f22d 2014-07-26 kinaba: #include <complex> 744af0f22d 2014-07-26 kinaba: #include <queue> 744af0f22d 2014-07-26 kinaba: #include <stack> 744af0f22d 2014-07-26 kinaba: #include <cmath> 744af0f22d 2014-07-26 kinaba: #include <cassert> 744af0f22d 2014-07-26 kinaba: #include <tuple> 744af0f22d 2014-07-26 kinaba: using namespace std; 744af0f22d 2014-07-26 kinaba: typedef long long LL; 744af0f22d 2014-07-26 kinaba: typedef complex<double> CMP; 744af0f22d 2014-07-26 kinaba: 744af0f22d 2014-07-26 kinaba: class DivisorsPower { public: 744af0f22d 2014-07-26 kinaba: long long findArgument(long long n) 744af0f22d 2014-07-26 kinaba: { 744af0f22d 2014-07-26 kinaba: LL cand = 1LL<<62; 744af0f22d 2014-07-26 kinaba: for(int p=2; p<=63; ++p) { 744af0f22d 2014-07-26 kinaba: LL xc = LL(pow(double(n), 1.0/p)); 744af0f22d 2014-07-26 kinaba: for(LL x=max(2LL,xc-100); x<=min(xc+100,n); ++x) 744af0f22d 2014-07-26 kinaba: if(ok(x,n)) 744af0f22d 2014-07-26 kinaba: cand = min(cand, x); 744af0f22d 2014-07-26 kinaba: } 744af0f22d 2014-07-26 kinaba: return (cand==(1LL<<62) ? -1 : cand); 744af0f22d 2014-07-26 kinaba: } 744af0f22d 2014-07-26 kinaba: 744af0f22d 2014-07-26 kinaba: int d(LL x) 744af0f22d 2014-07-26 kinaba: { 744af0f22d 2014-07-26 kinaba: int cnt = 1; 744af0f22d 2014-07-26 kinaba: for(int p=2; p*p<=x; ++p) 744af0f22d 2014-07-26 kinaba: if(x%p==0) { 744af0f22d 2014-07-26 kinaba: int k = 0; 744af0f22d 2014-07-26 kinaba: while(x%p==0) x/=p, ++k; 744af0f22d 2014-07-26 kinaba: cnt *= 1+k; 744af0f22d 2014-07-26 kinaba: } 744af0f22d 2014-07-26 kinaba: if(x>1) 744af0f22d 2014-07-26 kinaba: cnt *= 2; 744af0f22d 2014-07-26 kinaba: return cnt; 744af0f22d 2014-07-26 kinaba: } 744af0f22d 2014-07-26 kinaba: 744af0f22d 2014-07-26 kinaba: int ilog(LL x, LL n) 744af0f22d 2014-07-26 kinaba: { 744af0f22d 2014-07-26 kinaba: int cnt = 0; 744af0f22d 2014-07-26 kinaba: while(n%x==0) 744af0f22d 2014-07-26 kinaba: n/=x, ++cnt; 744af0f22d 2014-07-26 kinaba: return n>1 ? -1 : cnt; 744af0f22d 2014-07-26 kinaba: } 744af0f22d 2014-07-26 kinaba: 744af0f22d 2014-07-26 kinaba: 744af0f22d 2014-07-26 kinaba: bool ok(LL x, LL n) 744af0f22d 2014-07-26 kinaba: { 744af0f22d 2014-07-26 kinaba: return ilog(x, n) == d(x); 744af0f22d 2014-07-26 kinaba: } 744af0f22d 2014-07-26 kinaba: }; 744af0f22d 2014-07-26 kinaba: 744af0f22d 2014-07-26 kinaba: // BEGIN CUT HERE 744af0f22d 2014-07-26 kinaba: #include <ctime> 744af0f22d 2014-07-26 kinaba: double start_time; string timer() 744af0f22d 2014-07-26 kinaba: { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } 744af0f22d 2014-07-26 kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) 744af0f22d 2014-07-26 kinaba: { os << "{ "; 744af0f22d 2014-07-26 kinaba: for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) 744af0f22d 2014-07-26 kinaba: os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } 744af0f22d 2014-07-26 kinaba: void verify_case(const long long& Expected, const long long& Received) { 744af0f22d 2014-07-26 kinaba: bool ok = (Expected == Received); 744af0f22d 2014-07-26 kinaba: if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 744af0f22d 2014-07-26 kinaba: cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 744af0f22d 2014-07-26 kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 744af0f22d 2014-07-26 kinaba: #define END verify_case(_, DivisorsPower().findArgument(n));} 744af0f22d 2014-07-26 kinaba: int main(){ 744af0f22d 2014-07-26 kinaba: 744af0f22d 2014-07-26 kinaba: CASE(0) 744af0f22d 2014-07-26 kinaba: long long n = 4LL; 744af0f22d 2014-07-26 kinaba: long long _ = 2LL; 744af0f22d 2014-07-26 kinaba: END 744af0f22d 2014-07-26 kinaba: CASE(1) 744af0f22d 2014-07-26 kinaba: long long n = 10LL; 744af0f22d 2014-07-26 kinaba: long long _ = -1LL; 744af0f22d 2014-07-26 kinaba: END 744af0f22d 2014-07-26 kinaba: CASE(2) 744af0f22d 2014-07-26 kinaba: long long n = 64LL; 744af0f22d 2014-07-26 kinaba: long long _ = 4LL; 744af0f22d 2014-07-26 kinaba: END 744af0f22d 2014-07-26 kinaba: CASE(3) 744af0f22d 2014-07-26 kinaba: long long n = 10000LL; 744af0f22d 2014-07-26 kinaba: long long _ = 10LL; 744af0f22d 2014-07-26 kinaba: END 744af0f22d 2014-07-26 kinaba: CASE(4) 744af0f22d 2014-07-26 kinaba: long long n = 2498388559757689LL; 744af0f22d 2014-07-26 kinaba: long long _ = 49983883LL; 744af0f22d 2014-07-26 kinaba: END 744af0f22d 2014-07-26 kinaba: /* 744af0f22d 2014-07-26 kinaba: CASE(5) 744af0f22d 2014-07-26 kinaba: long long n = LL; 744af0f22d 2014-07-26 kinaba: long long _ = LL; 744af0f22d 2014-07-26 kinaba: END 744af0f22d 2014-07-26 kinaba: CASE(6) 744af0f22d 2014-07-26 kinaba: long long n = LL; 744af0f22d 2014-07-26 kinaba: long long _ = LL; 744af0f22d 2014-07-26 kinaba: END 744af0f22d 2014-07-26 kinaba: */ 744af0f22d 2014-07-26 kinaba: } 744af0f22d 2014-07-26 kinaba: // END CUT HERE