490a8ed924 2011-05-17 kinaba: #include <iostream> 490a8ed924 2011-05-17 kinaba: #include <sstream> 490a8ed924 2011-05-17 kinaba: #include <iomanip> 490a8ed924 2011-05-17 kinaba: #include <vector> 490a8ed924 2011-05-17 kinaba: #include <string> 490a8ed924 2011-05-17 kinaba: #include <map> 490a8ed924 2011-05-17 kinaba: #include <set> 490a8ed924 2011-05-17 kinaba: #include <algorithm> 490a8ed924 2011-05-17 kinaba: #include <numeric> 490a8ed924 2011-05-17 kinaba: #include <iterator> 490a8ed924 2011-05-17 kinaba: #include <functional> 490a8ed924 2011-05-17 kinaba: #include <complex> 490a8ed924 2011-05-17 kinaba: #include <queue> 490a8ed924 2011-05-17 kinaba: #include <stack> 490a8ed924 2011-05-17 kinaba: #include <cmath> 490a8ed924 2011-05-17 kinaba: #include <cassert> 490a8ed924 2011-05-17 kinaba: #include <cstring> 490a8ed924 2011-05-17 kinaba: using namespace std; 490a8ed924 2011-05-17 kinaba: typedef long long LL; 490a8ed924 2011-05-17 kinaba: typedef complex<double> CMP; 490a8ed924 2011-05-17 kinaba: 490a8ed924 2011-05-17 kinaba: class SetMultiples { public: 490a8ed924 2011-05-17 kinaba: long long smallestSubset(long long A, long long B, long long C, long long D) 490a8ed924 2011-05-17 kinaba: { 490a8ed924 2011-05-17 kinaba: vector< pair<LL,LL> > noneed( 1, make_pair(1,100000) ); 490a8ed924 2011-05-17 kinaba: 490a8ed924 2011-05-17 kinaba: LL cnt = 0; 490a8ed924 2011-05-17 kinaba: for(LL p=1; p<=100000; ++p) 490a8ed924 2011-05-17 kinaba: { 490a8ed924 2011-05-17 kinaba: if( A<=p&&p<=B || C<=p&&p<=D ) 490a8ed924 2011-05-17 kinaba: if( need(p, A, B, C, D) ) 490a8ed924 2011-05-17 kinaba: ++cnt; 490a8ed924 2011-05-17 kinaba: if( p > 1 ) { 490a8ed924 2011-05-17 kinaba: add(noneed, p, A, B); 490a8ed924 2011-05-17 kinaba: add(noneed, p, C, D); 490a8ed924 2011-05-17 kinaba: } 490a8ed924 2011-05-17 kinaba: } 490a8ed924 2011-05-17 kinaba: sort(noneed.begin(), noneed.end(), &my_order); 490a8ed924 2011-05-17 kinaba: LL a = count_need(noneed, A, B); 490a8ed924 2011-05-17 kinaba: LL b = count_need(noneed, C, D); 490a8ed924 2011-05-17 kinaba: return cnt + a + b; 490a8ed924 2011-05-17 kinaba: } 490a8ed924 2011-05-17 kinaba: 490a8ed924 2011-05-17 kinaba: static bool need(LL p, LL A, LL B, LL C, LL D) 490a8ed924 2011-05-17 kinaba: { 490a8ed924 2011-05-17 kinaba: return !covered(p,A,B) && !covered(p,C,D); 490a8ed924 2011-05-17 kinaba: } 490a8ed924 2011-05-17 kinaba: 490a8ed924 2011-05-17 kinaba: static bool covered(LL p, LL A, LL B) 490a8ed924 2011-05-17 kinaba: { 490a8ed924 2011-05-17 kinaba: LL lo = A%p==0 ? A/p : A/p+1; 490a8ed924 2011-05-17 kinaba: LL hi = B/p; 490a8ed924 2011-05-17 kinaba: return ( lo<=hi && 2<=hi ); 490a8ed924 2011-05-17 kinaba: } 490a8ed924 2011-05-17 kinaba: 490a8ed924 2011-05-17 kinaba: static void add(vector< pair<LL,LL> >& noneed, LL p, LL A, LL B) 490a8ed924 2011-05-17 kinaba: { 490a8ed924 2011-05-17 kinaba: LL lo = A%p==0 ? A/p : A/p+1; 490a8ed924 2011-05-17 kinaba: LL hi = B/p; 490a8ed924 2011-05-17 kinaba: if( lo <= hi ) 490a8ed924 2011-05-17 kinaba: noneed.push_back( make_pair(lo,hi) ); 490a8ed924 2011-05-17 kinaba: } 490a8ed924 2011-05-17 kinaba: 490a8ed924 2011-05-17 kinaba: static bool my_order( const pair<LL,LL>& lhs, const pair<LL,LL>& rhs ) 490a8ed924 2011-05-17 kinaba: { 490a8ed924 2011-05-17 kinaba: if( lhs.second != rhs.second ) 490a8ed924 2011-05-17 kinaba: return lhs.second > rhs.second; 490a8ed924 2011-05-17 kinaba: return lhs.first < rhs.first; 490a8ed924 2011-05-17 kinaba: } 490a8ed924 2011-05-17 kinaba: 490a8ed924 2011-05-17 kinaba: static LL count_need(const vector< pair<LL,LL> >& noneed, LL A, LL B) 490a8ed924 2011-05-17 kinaba: { 490a8ed924 2011-05-17 kinaba: LL cnt = 0; 490a8ed924 2011-05-17 kinaba: LL highest_need = B; 490a8ed924 2011-05-17 kinaba: for(int i=0; i<noneed.size(); ++i) 490a8ed924 2011-05-17 kinaba: { 490a8ed924 2011-05-17 kinaba: LL lo = noneed[i].first; 490a8ed924 2011-05-17 kinaba: LL hi = noneed[i].second; 490a8ed924 2011-05-17 kinaba: if( hi < highest_need ) 490a8ed924 2011-05-17 kinaba: cnt += max(0LL, highest_need - max(hi,A-1)); 490a8ed924 2011-05-17 kinaba: highest_need = min(highest_need, lo-1); 490a8ed924 2011-05-17 kinaba: if( highest_need < A ) 490a8ed924 2011-05-17 kinaba: return cnt; 490a8ed924 2011-05-17 kinaba: } 490a8ed924 2011-05-17 kinaba: return cnt + (highest_need - A + 1); 490a8ed924 2011-05-17 kinaba: } 490a8ed924 2011-05-17 kinaba: }; 490a8ed924 2011-05-17 kinaba: 490a8ed924 2011-05-17 kinaba: // BEGIN CUT HERE 490a8ed924 2011-05-17 kinaba: #include <ctime> 490a8ed924 2011-05-17 kinaba: double start_time; string timer() 490a8ed924 2011-05-17 kinaba: { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } 490a8ed924 2011-05-17 kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) 490a8ed924 2011-05-17 kinaba: { os << "{ "; 490a8ed924 2011-05-17 kinaba: for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) 490a8ed924 2011-05-17 kinaba: os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } 490a8ed924 2011-05-17 kinaba: void verify_case(const long long& Expected, const long long& Received) { 490a8ed924 2011-05-17 kinaba: bool ok = (Expected == Received); 490a8ed924 2011-05-17 kinaba: if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 490a8ed924 2011-05-17 kinaba: cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 490a8ed924 2011-05-17 kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 490a8ed924 2011-05-17 kinaba: #define END verify_case(_, SetMultiples().smallestSubset(A, B, C, D));} 490a8ed924 2011-05-17 kinaba: int main(){ 490a8ed924 2011-05-17 kinaba: 490a8ed924 2011-05-17 kinaba: CASE(0) 490a8ed924 2011-05-17 kinaba: long long A = 1LL; 490a8ed924 2011-05-17 kinaba: long long B = 1LL; 490a8ed924 2011-05-17 kinaba: long long C = 2LL; 490a8ed924 2011-05-17 kinaba: long long D = 2LL; 490a8ed924 2011-05-17 kinaba: long long _ = 1LL; 490a8ed924 2011-05-17 kinaba: END 490a8ed924 2011-05-17 kinaba: CASE(1) 490a8ed924 2011-05-17 kinaba: long long A = 1LL; 490a8ed924 2011-05-17 kinaba: long long B = 2LL; 490a8ed924 2011-05-17 kinaba: long long C = 3LL; 490a8ed924 2011-05-17 kinaba: long long D = 4LL; 490a8ed924 2011-05-17 kinaba: long long _ = 2LL; 490a8ed924 2011-05-17 kinaba: END 490a8ed924 2011-05-17 kinaba: CASE(2) 490a8ed924 2011-05-17 kinaba: long long A = 2LL; 490a8ed924 2011-05-17 kinaba: long long B = 3LL; 490a8ed924 2011-05-17 kinaba: long long C = 5LL; 490a8ed924 2011-05-17 kinaba: long long D = 7LL; 490a8ed924 2011-05-17 kinaba: long long _ = 3LL; 490a8ed924 2011-05-17 kinaba: END 490a8ed924 2011-05-17 kinaba: CASE(3) 490a8ed924 2011-05-17 kinaba: long long A = 1LL; 490a8ed924 2011-05-17 kinaba: long long B = 10LL; 490a8ed924 2011-05-17 kinaba: long long C = 100LL; 490a8ed924 2011-05-17 kinaba: long long D = 1000LL; 490a8ed924 2011-05-17 kinaba: long long _ = 500LL; 490a8ed924 2011-05-17 kinaba: END 490a8ed924 2011-05-17 kinaba: CASE(4) 490a8ed924 2011-05-17 kinaba: long long A = 1000000000LL; 490a8ed924 2011-05-17 kinaba: long long B = 2000000000LL; 490a8ed924 2011-05-17 kinaba: long long C = 9000000000LL; 490a8ed924 2011-05-17 kinaba: long long D = 10000000000LL; 490a8ed924 2011-05-17 kinaba: long long _ = 1254365078LL; 490a8ed924 2011-05-17 kinaba: END 490a8ed924 2011-05-17 kinaba: CASE(5) 490a8ed924 2011-05-17 kinaba: long long A = 1LL; 490a8ed924 2011-05-17 kinaba: long long B = 1000000000LL; 490a8ed924 2011-05-17 kinaba: long long C = 2000000000LL; 490a8ed924 2011-05-17 kinaba: long long D = 10000000000LL; 490a8ed924 2011-05-17 kinaba: long long _ = -1LL; 490a8ed924 2011-05-17 kinaba: END 490a8ed924 2011-05-17 kinaba: CASE(6) 490a8ed924 2011-05-17 kinaba: long long A = 1LL; 490a8ed924 2011-05-17 kinaba: long long B = 2LL; 490a8ed924 2011-05-17 kinaba: long long C = 3LL; 490a8ed924 2011-05-17 kinaba: long long D = 5LL; 490a8ed924 2011-05-17 kinaba: long long _ = 3LL; 490a8ed924 2011-05-17 kinaba: END 490a8ed924 2011-05-17 kinaba: 490a8ed924 2011-05-17 kinaba: } 490a8ed924 2011-05-17 kinaba: // END CUT HERE