bc2785b91d 2012-08-17 kinaba: #include <iostream> bc2785b91d 2012-08-17 kinaba: #include <sstream> bc2785b91d 2012-08-17 kinaba: #include <iomanip> bc2785b91d 2012-08-17 kinaba: #include <vector> bc2785b91d 2012-08-17 kinaba: #include <string> bc2785b91d 2012-08-17 kinaba: #include <map> bc2785b91d 2012-08-17 kinaba: #include <set> bc2785b91d 2012-08-17 kinaba: #include <algorithm> bc2785b91d 2012-08-17 kinaba: #include <numeric> bc2785b91d 2012-08-17 kinaba: #include <iterator> bc2785b91d 2012-08-17 kinaba: #include <functional> bc2785b91d 2012-08-17 kinaba: #include <complex> bc2785b91d 2012-08-17 kinaba: #include <queue> bc2785b91d 2012-08-17 kinaba: #include <stack> bc2785b91d 2012-08-17 kinaba: #include <cmath> bc2785b91d 2012-08-17 kinaba: #include <cassert> bc2785b91d 2012-08-17 kinaba: using namespace std; bc2785b91d 2012-08-17 kinaba: typedef long long LL; bc2785b91d 2012-08-17 kinaba: typedef long double LD; bc2785b91d 2012-08-17 kinaba: typedef complex<LD> CMP; bc2785b91d 2012-08-17 kinaba: bc2785b91d 2012-08-17 kinaba: class HolyNumbers { public: bc2785b91d 2012-08-17 kinaba: vector<LL> erat(int N) bc2785b91d 2012-08-17 kinaba: { bc2785b91d 2012-08-17 kinaba: vector<LL> ps; bc2785b91d 2012-08-17 kinaba: vector<bool> is_prime(N+1, true); bc2785b91d 2012-08-17 kinaba: for(int p=2; p<=N; ++p) bc2785b91d 2012-08-17 kinaba: if(is_prime[p]) { bc2785b91d 2012-08-17 kinaba: ps.push_back(p); bc2785b91d 2012-08-17 kinaba: for(int q=p+p; q<=N; q+=p) bc2785b91d 2012-08-17 kinaba: is_prime[q] = false; bc2785b91d 2012-08-17 kinaba: } bc2785b91d 2012-08-17 kinaba: return ps; bc2785b91d 2012-08-17 kinaba: } bc2785b91d 2012-08-17 kinaba: bc2785b91d 2012-08-17 kinaba: long long count(long long upTo, int maximalPrime) bc2785b91d 2012-08-17 kinaba: { bc2785b91d 2012-08-17 kinaba: vector<LL> ps = erat(maximalPrime); bc2785b91d 2012-08-17 kinaba: return naive(ps, 0, upTo); bc2785b91d 2012-08-17 kinaba: } bc2785b91d 2012-08-17 kinaba: bc2785b91d 2012-08-17 kinaba: LL naive(const vector<LL>& ps, int i, LL upto) bc2785b91d 2012-08-17 kinaba: { bc2785b91d 2012-08-17 kinaba: if( i==ps.size() || upto<ps[i] ) bc2785b91d 2012-08-17 kinaba: return 1; bc2785b91d 2012-08-17 kinaba: bc2785b91d 2012-08-17 kinaba: if( upto < ps[i]*ps[i] ) bc2785b91d 2012-08-17 kinaba: { bc2785b91d 2012-08-17 kinaba: int k = upper_bound(ps.begin()+i, ps.end(), upto) - ps.begin(); bc2785b91d 2012-08-17 kinaba: return (k-i)+1; bc2785b91d 2012-08-17 kinaba: } bc2785b91d 2012-08-17 kinaba: LL sum = naive(ps, i+1, upto); bc2785b91d 2012-08-17 kinaba: for(LL p=ps[i], pk=p; pk<=upto; pk*=p*p) bc2785b91d 2012-08-17 kinaba: sum += naive(ps, i+1, upto/pk); bc2785b91d 2012-08-17 kinaba: return sum; bc2785b91d 2012-08-17 kinaba: } bc2785b91d 2012-08-17 kinaba: }; bc2785b91d 2012-08-17 kinaba: bc2785b91d 2012-08-17 kinaba: // BEGIN CUT HERE bc2785b91d 2012-08-17 kinaba: #include <ctime> bc2785b91d 2012-08-17 kinaba: double start_time; string timer() bc2785b91d 2012-08-17 kinaba: { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } bc2785b91d 2012-08-17 kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) bc2785b91d 2012-08-17 kinaba: { os << "{ "; bc2785b91d 2012-08-17 kinaba: for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) bc2785b91d 2012-08-17 kinaba: os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } bc2785b91d 2012-08-17 kinaba: void verify_case(const long long& Expected, const long long& Received) { bc2785b91d 2012-08-17 kinaba: bool ok = (Expected == Received); bc2785b91d 2012-08-17 kinaba: if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; bc2785b91d 2012-08-17 kinaba: cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } bc2785b91d 2012-08-17 kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); bc2785b91d 2012-08-17 kinaba: #define END verify_case(_, HolyNumbers().count(upTo, maximalPrime));} bc2785b91d 2012-08-17 kinaba: int main(){ bc2785b91d 2012-08-17 kinaba: bc2785b91d 2012-08-17 kinaba: CASE(0) bc2785b91d 2012-08-17 kinaba: long long upTo = 10LL; bc2785b91d 2012-08-17 kinaba: int maximalPrime = 100; bc2785b91d 2012-08-17 kinaba: long long _ = 8LL; bc2785b91d 2012-08-17 kinaba: END bc2785b91d 2012-08-17 kinaba: CASE(1) bc2785b91d 2012-08-17 kinaba: long long upTo = 10LL; bc2785b91d 2012-08-17 kinaba: int maximalPrime = 3; bc2785b91d 2012-08-17 kinaba: long long _ = 5LL; bc2785b91d 2012-08-17 kinaba: END bc2785b91d 2012-08-17 kinaba: CASE(2) bc2785b91d 2012-08-17 kinaba: long long upTo = 123LL; bc2785b91d 2012-08-17 kinaba: int maximalPrime = 12; bc2785b91d 2012-08-17 kinaba: long long _ = 32LL; bc2785b91d 2012-08-17 kinaba: END bc2785b91d 2012-08-17 kinaba: CASE(3) bc2785b91d 2012-08-17 kinaba: long long upTo = 123LL; bc2785b91d 2012-08-17 kinaba: int maximalPrime = 456; bc2785b91d 2012-08-17 kinaba: long long _ = 88LL; bc2785b91d 2012-08-17 kinaba: END bc2785b91d 2012-08-17 kinaba: CASE(4) bc2785b91d 2012-08-17 kinaba: long long upTo = 123456789LL; bc2785b91d 2012-08-17 kinaba: int maximalPrime = 12345; bc2785b91d 2012-08-17 kinaba: long long _ = 25994500LL; bc2785b91d 2012-08-17 kinaba: END bc2785b91d 2012-08-17 kinaba: CASE(5) bc2785b91d 2012-08-17 kinaba: long long upTo = 10000000000LL; bc2785b91d 2012-08-17 kinaba: int maximalPrime = 1000000; bc2785b91d 2012-08-17 kinaba: long long _ = -1LL; bc2785b91d 2012-08-17 kinaba: END bc2785b91d 2012-08-17 kinaba: CASE(6) bc2785b91d 2012-08-17 kinaba: long long upTo = 10000000000LL; bc2785b91d 2012-08-17 kinaba: int maximalPrime = 100; bc2785b91d 2012-08-17 kinaba: long long _ = -1LL; bc2785b91d 2012-08-17 kinaba: END bc2785b91d 2012-08-17 kinaba: } bc2785b91d 2012-08-17 kinaba: // END CUT HERE