26aa079da8 2015-01-02        kinaba: #include <iostream>
26aa079da8 2015-01-02        kinaba: #include <sstream>
26aa079da8 2015-01-02        kinaba: #include <iomanip>
26aa079da8 2015-01-02        kinaba: #include <vector>
26aa079da8 2015-01-02        kinaba: #include <string>
26aa079da8 2015-01-02        kinaba: #include <map>
26aa079da8 2015-01-02        kinaba: #include <set>
26aa079da8 2015-01-02        kinaba: #include <algorithm>
26aa079da8 2015-01-02        kinaba: #include <numeric>
26aa079da8 2015-01-02        kinaba: #include <iterator>
26aa079da8 2015-01-02        kinaba: #include <functional>
26aa079da8 2015-01-02        kinaba: #include <complex>
26aa079da8 2015-01-02        kinaba: #include <queue>
26aa079da8 2015-01-02        kinaba: #include <stack>
26aa079da8 2015-01-02        kinaba: #include <cmath>
26aa079da8 2015-01-02        kinaba: #include <cassert>
26aa079da8 2015-01-02        kinaba: #include <tuple>
26aa079da8 2015-01-02        kinaba: using namespace std;
26aa079da8 2015-01-02        kinaba: typedef long long LL;
26aa079da8 2015-01-02        kinaba: typedef complex<double> CMP;
26aa079da8 2015-01-02        kinaba: 
26aa079da8 2015-01-02        kinaba: class TheKingsFactorization { public:
26aa079da8 2015-01-02        kinaba: 	vector<long long> getVector(long long N, vector<long long> primes)
26aa079da8 2015-01-02        kinaba: 	{
26aa079da8 2015-01-02        kinaba: 		vector<LL> ans;
26aa079da8 2015-01-02        kinaba: 		for(int p=2; p<=1000001; ++p)
26aa079da8 2015-01-02        kinaba: 			while(N%p == 0) {
26aa079da8 2015-01-02        kinaba: 				ans.push_back(p);
26aa079da8 2015-01-02        kinaba: 				N /= p;
26aa079da8 2015-01-02        kinaba: 			}
26aa079da8 2015-01-02        kinaba: 
26aa079da8 2015-01-02        kinaba: 		// all primes <= cbrt(N) is reported. we have at most 2 more.
26aa079da8 2015-01-02        kinaba: 
26aa079da8 2015-01-02        kinaba: 		const LL last_p = primes.back();
26aa079da8 2015-01-02        kinaba: 		if(N%last_p==0 && N!=last_p) {
26aa079da8 2015-01-02        kinaba: 			ans.push_back(min(N/last_p, last_p));
26aa079da8 2015-01-02        kinaba: 			ans.push_back(max(N/last_p, last_p));
26aa079da8 2015-01-02        kinaba: 			N = 1;
26aa079da8 2015-01-02        kinaba: 		}
26aa079da8 2015-01-02        kinaba: 
26aa079da8 2015-01-02        kinaba: 		if(N!=1)
26aa079da8 2015-01-02        kinaba: 			ans.push_back(N);
26aa079da8 2015-01-02        kinaba: 
26aa079da8 2015-01-02        kinaba: 		return ans;
26aa079da8 2015-01-02        kinaba: 	}
26aa079da8 2015-01-02        kinaba: };
26aa079da8 2015-01-02        kinaba: 
26aa079da8 2015-01-02        kinaba: // BEGIN CUT HERE
26aa079da8 2015-01-02        kinaba: #include <ctime>
26aa079da8 2015-01-02        kinaba: double start_time; string timer()
26aa079da8 2015-01-02        kinaba:  { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
26aa079da8 2015-01-02        kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
26aa079da8 2015-01-02        kinaba:  { os << "{ ";
26aa079da8 2015-01-02        kinaba:    for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
26aa079da8 2015-01-02        kinaba:    os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
26aa079da8 2015-01-02        kinaba: void verify_case(const vector<long long>& Expected, const vector<long long>& Received) {
26aa079da8 2015-01-02        kinaba:  bool ok = (Expected == Received);
26aa079da8 2015-01-02        kinaba:  if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
26aa079da8 2015-01-02        kinaba:  cerr << "\to: " << Expected << endl << "\tx: " << Received << endl; } }
26aa079da8 2015-01-02        kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
26aa079da8 2015-01-02        kinaba: #define END	 verify_case(_, TheKingsFactorization().getVector(N, primes));}
26aa079da8 2015-01-02        kinaba: int main(){
26aa079da8 2015-01-02        kinaba: 
26aa079da8 2015-01-02        kinaba: CASE(0)
26aa079da8 2015-01-02        kinaba: 	long long N = 12LL;
26aa079da8 2015-01-02        kinaba: 	long long primes_[] = {2, 3};
26aa079da8 2015-01-02        kinaba: 	  vector<long long> primes(primes_, primes_+sizeof(primes_)/sizeof(*primes_));
26aa079da8 2015-01-02        kinaba: 	long long __[] = {2, 2, 3 };
26aa079da8 2015-01-02        kinaba: 	  vector<long long> _(__, __+sizeof(__)/sizeof(*__));
26aa079da8 2015-01-02        kinaba: END
26aa079da8 2015-01-02        kinaba: CASE(1)
26aa079da8 2015-01-02        kinaba: 	long long N = 7LL;
26aa079da8 2015-01-02        kinaba: 	long long primes_[] = {7};
26aa079da8 2015-01-02        kinaba: 	  vector<long long> primes(primes_, primes_+sizeof(primes_)/sizeof(*primes_));
26aa079da8 2015-01-02        kinaba: 	long long __[] = {7 };
26aa079da8 2015-01-02        kinaba: 	  vector<long long> _(__, __+sizeof(__)/sizeof(*__));
26aa079da8 2015-01-02        kinaba: END
26aa079da8 2015-01-02        kinaba: CASE(2)
26aa079da8 2015-01-02        kinaba: 	long long N = 1764LL;
26aa079da8 2015-01-02        kinaba: 	long long primes_[] = {2, 3, 7};
26aa079da8 2015-01-02        kinaba: 	  vector<long long> primes(primes_, primes_+sizeof(primes_)/sizeof(*primes_));
26aa079da8 2015-01-02        kinaba: 	long long __[] = {2, 2, 3, 3, 7, 7 };
26aa079da8 2015-01-02        kinaba: 	  vector<long long> _(__, __+sizeof(__)/sizeof(*__));
26aa079da8 2015-01-02        kinaba: END
26aa079da8 2015-01-02        kinaba: CASE(3)
26aa079da8 2015-01-02        kinaba: 	long long N = 49LL;
26aa079da8 2015-01-02        kinaba: 	long long primes_[] = {7};
26aa079da8 2015-01-02        kinaba: 	  vector<long long> primes(primes_, primes_+sizeof(primes_)/sizeof(*primes_));
26aa079da8 2015-01-02        kinaba: 	long long __[] = {7, 7 };
26aa079da8 2015-01-02        kinaba: 	  vector<long long> _(__, __+sizeof(__)/sizeof(*__));
26aa079da8 2015-01-02        kinaba: END
26aa079da8 2015-01-02        kinaba: CASE(4)
26aa079da8 2015-01-02        kinaba: 	long long N = 210LL;
26aa079da8 2015-01-02        kinaba: 	long long primes_[] = {2, 5};
26aa079da8 2015-01-02        kinaba: 	  vector<long long> primes(primes_, primes_+sizeof(primes_)/sizeof(*primes_));
26aa079da8 2015-01-02        kinaba: 	long long __[] = {2, 3, 5, 7 };
26aa079da8 2015-01-02        kinaba: 	  vector<long long> _(__, __+sizeof(__)/sizeof(*__));
26aa079da8 2015-01-02        kinaba: END
26aa079da8 2015-01-02        kinaba: CASE(5)
26aa079da8 2015-01-02        kinaba: 	long long N = 100000LL;
26aa079da8 2015-01-02        kinaba: 	long long primes_[] = {2, 2, 2, 5, 5};
26aa079da8 2015-01-02        kinaba: 	  vector<long long> primes(primes_, primes_+sizeof(primes_)/sizeof(*primes_));
26aa079da8 2015-01-02        kinaba: 	long long __[] = {2, 2, 2, 2, 2, 5, 5, 5, 5, 5 };
26aa079da8 2015-01-02        kinaba: 	  vector<long long> _(__, __+sizeof(__)/sizeof(*__));
26aa079da8 2015-01-02        kinaba: END
26aa079da8 2015-01-02        kinaba: CASE(6)
26aa079da8 2015-01-02        kinaba: 	long long N = 540000003780LL;
26aa079da8 2015-01-02        kinaba: 	long long primes_[] = {2,3,3,1000000007};
26aa079da8 2015-01-02        kinaba: 	  vector<long long> primes(primes_, primes_+sizeof(primes_)/sizeof(*primes_));
26aa079da8 2015-01-02        kinaba: 	  long long __[] = {2,2,3,3,3,5,1000000007};
26aa079da8 2015-01-02        kinaba: 	  vector<long long> _(__, __+sizeof(__)/sizeof(*__));
26aa079da8 2015-01-02        kinaba: END
26aa079da8 2015-01-02        kinaba: CASE(7)
26aa079da8 2015-01-02        kinaba: 	long long N = 2700000018900LL;
26aa079da8 2015-01-02        kinaba: 	long long primes_[] = {2,3,3,5};
26aa079da8 2015-01-02        kinaba: 	  vector<long long> primes(primes_, primes_+sizeof(primes_)/sizeof(*primes_));
26aa079da8 2015-01-02        kinaba: 	  long long __[] = {2,2,3,3,3,5,5,1000000007};
26aa079da8 2015-01-02        kinaba: 	  vector<long long> _(__, __+sizeof(__)/sizeof(*__));
26aa079da8 2015-01-02        kinaba: END
26aa079da8 2015-01-02        kinaba: }
26aa079da8 2015-01-02        kinaba: // END CUT HERE