42f877f59c 2012-12-21 kinaba: #include <iostream> 42f877f59c 2012-12-21 kinaba: #include <sstream> 42f877f59c 2012-12-21 kinaba: #include <iomanip> 42f877f59c 2012-12-21 kinaba: #include <vector> 42f877f59c 2012-12-21 kinaba: #include <string> 42f877f59c 2012-12-21 kinaba: #include <map> 42f877f59c 2012-12-21 kinaba: #include <set> 42f877f59c 2012-12-21 kinaba: #include <algorithm> 42f877f59c 2012-12-21 kinaba: #include <numeric> 42f877f59c 2012-12-21 kinaba: #include <iterator> 42f877f59c 2012-12-21 kinaba: #include <functional> 42f877f59c 2012-12-21 kinaba: #include <complex> 42f877f59c 2012-12-21 kinaba: #include <queue> 42f877f59c 2012-12-21 kinaba: #include <stack> 42f877f59c 2012-12-21 kinaba: #include <cmath> 42f877f59c 2012-12-21 kinaba: #include <cassert> 42f877f59c 2012-12-21 kinaba: using namespace std; 42f877f59c 2012-12-21 kinaba: typedef long long LL; 42f877f59c 2012-12-21 kinaba: typedef long double LD; 42f877f59c 2012-12-21 kinaba: typedef complex<LD> CMP; 42f877f59c 2012-12-21 kinaba: 42f877f59c 2012-12-21 kinaba: class TheDivisionGame { public: 42f877f59c 2012-12-21 kinaba: long long countWinningIntervals(int L, int R) 42f877f59c 2012-12-21 kinaba: { 42f877f59c 2012-12-21 kinaba: // eratos --------------------------------- 42f877f59c 2012-12-21 kinaba: vector<int> ps; 42f877f59c 2012-12-21 kinaba: { 42f877f59c 2012-12-21 kinaba: static const int N = 50000; 42f877f59c 2012-12-21 kinaba: vector<bool> isp(N+1, true); 42f877f59c 2012-12-21 kinaba: for(int p=2; p<=N; ++p) 42f877f59c 2012-12-21 kinaba: if( isp[p] ) { 42f877f59c 2012-12-21 kinaba: ps.push_back(p); 42f877f59c 2012-12-21 kinaba: for(int q=p+p; q<=N; q+=p) 42f877f59c 2012-12-21 kinaba: isp[q] = false; 42f877f59c 2012-12-21 kinaba: } 42f877f59c 2012-12-21 kinaba: } 42f877f59c 2012-12-21 kinaba: 42f877f59c 2012-12-21 kinaba: // prime decomposition -------------------- 42f877f59c 2012-12-21 kinaba: vector< vector<int> > pd(R-L+1); 42f877f59c 2012-12-21 kinaba: vector<int> rm(R-L+1); 42f877f59c 2012-12-21 kinaba: for(int v=L; v<=R; ++v) 42f877f59c 2012-12-21 kinaba: rm[v-L] = v; 42f877f59c 2012-12-21 kinaba: 42f877f59c 2012-12-21 kinaba: for(int i=0; i<ps.size(); ++i) 42f877f59c 2012-12-21 kinaba: { 42f877f59c 2012-12-21 kinaba: int p = ps[i]; 42f877f59c 2012-12-21 kinaba: for(int q=(L+p-1)/p*p; q<=R; q+=p) 42f877f59c 2012-12-21 kinaba: { 42f877f59c 2012-12-21 kinaba: int& r = rm[q-L]; 42f877f59c 2012-12-21 kinaba: int qn = 0; 42f877f59c 2012-12-21 kinaba: while(r%p==0) qn++, r/=p; 42f877f59c 2012-12-21 kinaba: pd[q-L].push_back(qn); 42f877f59c 2012-12-21 kinaba: } 42f877f59c 2012-12-21 kinaba: } 42f877f59c 2012-12-21 kinaba: 42f877f59c 2012-12-21 kinaba: for(int v=L; v<=R; ++v) 42f877f59c 2012-12-21 kinaba: if(rm[v-L] > 1) 42f877f59c 2012-12-21 kinaba: pd[v-L].push_back(1); 42f877f59c 2012-12-21 kinaba: 42f877f59c 2012-12-21 kinaba: // grundy ------------------------------------ 42f877f59c 2012-12-21 kinaba: vector<int> nim; 42f877f59c 2012-12-21 kinaba: for(int i=0; i<pd.size(); ++i) { 42f877f59c 2012-12-21 kinaba: nim.push_back(nim_calc(pd[i])); 42f877f59c 2012-12-21 kinaba: } 42f877f59c 2012-12-21 kinaba: 42f877f59c 2012-12-21 kinaba: // xorsum ------------------------------------ 42f877f59c 2012-12-21 kinaba: vector<int> sum; 42f877f59c 2012-12-21 kinaba: map<int, LL> hist; 42f877f59c 2012-12-21 kinaba: sum.push_back(0); 42f877f59c 2012-12-21 kinaba: hist[sum.back()] ++; 42f877f59c 2012-12-21 kinaba: for(int i=0; i<nim.size(); ++i) { 42f877f59c 2012-12-21 kinaba: sum.push_back(sum.back() ^ nim[i]); 42f877f59c 2012-12-21 kinaba: hist[sum.back()] ++; 42f877f59c 2012-12-21 kinaba: } 42f877f59c 2012-12-21 kinaba: 42f877f59c 2012-12-21 kinaba: LL lose = 0; 42f877f59c 2012-12-21 kinaba: for(map<int,LL>::iterator it=hist.begin(); it!=hist.end(); ++it) 42f877f59c 2012-12-21 kinaba: lose += it->second * (it->second-1) / 2; 42f877f59c 2012-12-21 kinaba: LL w = R-L+2; 42f877f59c 2012-12-21 kinaba: LL total = w*(w-1)/2; 42f877f59c 2012-12-21 kinaba: return total - lose; 42f877f59c 2012-12-21 kinaba: } 42f877f59c 2012-12-21 kinaba: 42f877f59c 2012-12-21 kinaba: int nim_calc(vector<int> sig) 42f877f59c 2012-12-21 kinaba: { 42f877f59c 2012-12-21 kinaba: if( sig.empty() ) 42f877f59c 2012-12-21 kinaba: return 0; 42f877f59c 2012-12-21 kinaba: int v = sig[0]; 42f877f59c 2012-12-21 kinaba: for(int i=1; i<sig.size(); ++i) 42f877f59c 2012-12-21 kinaba: v = merge(v, sig[i]); 42f877f59c 2012-12-21 kinaba: return v; 42f877f59c 2012-12-21 kinaba: } 42f877f59c 2012-12-21 kinaba: 42f877f59c 2012-12-21 kinaba: map<pair<int,int>, int> memo; 42f877f59c 2012-12-21 kinaba: int merge(int a, int b) 42f877f59c 2012-12-21 kinaba: { 42f877f59c 2012-12-21 kinaba: if(a>b) swap(a,b); 42f877f59c 2012-12-21 kinaba: if(a==0) 42f877f59c 2012-12-21 kinaba: return b; 42f877f59c 2012-12-21 kinaba: pair<int,int> key(a,b); 42f877f59c 2012-12-21 kinaba: if(memo.count(key)) 42f877f59c 2012-12-21 kinaba: return memo[key]; 42f877f59c 2012-12-21 kinaba: 42f877f59c 2012-12-21 kinaba: vector<bool> used; 42f877f59c 2012-12-21 kinaba: for(int x=0; x<=a; ++x) 42f877f59c 2012-12-21 kinaba: for(int y=0; y<=b; ++y) 42f877f59c 2012-12-21 kinaba: if(x!=a || y!=b) 42f877f59c 2012-12-21 kinaba: { 42f877f59c 2012-12-21 kinaba: int k = merge(x, y); 42f877f59c 2012-12-21 kinaba: if(used.size()<=k) used.resize(k+1); 42f877f59c 2012-12-21 kinaba: used[k] = true; 42f877f59c 2012-12-21 kinaba: } 42f877f59c 2012-12-21 kinaba: 42f877f59c 2012-12-21 kinaba: used.push_back(false); 42f877f59c 2012-12-21 kinaba: return memo[key] = find(used.begin(), used.end(), false) - used.begin(); 42f877f59c 2012-12-21 kinaba: } 42f877f59c 2012-12-21 kinaba: }; 42f877f59c 2012-12-21 kinaba: 42f877f59c 2012-12-21 kinaba: // BEGIN CUT HERE 42f877f59c 2012-12-21 kinaba: #include <ctime> 42f877f59c 2012-12-21 kinaba: double start_time; string timer() 42f877f59c 2012-12-21 kinaba: { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } 42f877f59c 2012-12-21 kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) 42f877f59c 2012-12-21 kinaba: { os << "{ "; 42f877f59c 2012-12-21 kinaba: for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) 42f877f59c 2012-12-21 kinaba: os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } 42f877f59c 2012-12-21 kinaba: void verify_case(const long long& Expected, const long long& Received) { 42f877f59c 2012-12-21 kinaba: bool ok = (Expected == Received); 42f877f59c 2012-12-21 kinaba: if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 42f877f59c 2012-12-21 kinaba: cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 42f877f59c 2012-12-21 kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 42f877f59c 2012-12-21 kinaba: #define END verify_case(_, TheDivisionGame().countWinningIntervals(L, R));} 42f877f59c 2012-12-21 kinaba: int main(){ 42f877f59c 2012-12-21 kinaba: CASE(0) 42f877f59c 2012-12-21 kinaba: int L = 9; 42f877f59c 2012-12-21 kinaba: int R = 10; 42f877f59c 2012-12-21 kinaba: long long _ = 2LL; 42f877f59c 2012-12-21 kinaba: END 42f877f59c 2012-12-21 kinaba: CASE(1) 42f877f59c 2012-12-21 kinaba: int L = 2; 42f877f59c 2012-12-21 kinaba: int R = 5; 42f877f59c 2012-12-21 kinaba: long long _ = 9LL; 42f877f59c 2012-12-21 kinaba: END 42f877f59c 2012-12-21 kinaba: CASE(2) 42f877f59c 2012-12-21 kinaba: int L = 2; 42f877f59c 2012-12-21 kinaba: int R = 6; 42f877f59c 2012-12-21 kinaba: long long _ = 13LL; 42f877f59c 2012-12-21 kinaba: END 42f877f59c 2012-12-21 kinaba: CASE(3) 42f877f59c 2012-12-21 kinaba: int L = 2; 42f877f59c 2012-12-21 kinaba: int R = 100; 42f877f59c 2012-12-21 kinaba: long long _ = 4345LL; 42f877f59c 2012-12-21 kinaba: END 42f877f59c 2012-12-21 kinaba: CASE(4) 42f877f59c 2012-12-21 kinaba: int L = 12566125; 42f877f59c 2012-12-21 kinaba: int R = 12567777; 42f877f59c 2012-12-21 kinaba: long long _ = 1313432LL; 42f877f59c 2012-12-21 kinaba: END 42f877f59c 2012-12-21 kinaba: CASE(5) 42f877f59c 2012-12-21 kinaba: int L = 1000000000; 42f877f59c 2012-12-21 kinaba: int R = 1001000000; 42f877f59c 2012-12-21 kinaba: long long _ = -1LL; 42f877f59c 2012-12-21 kinaba: END 42f877f59c 2012-12-21 kinaba: CASE(6) 42f877f59c 2012-12-21 kinaba: int L = 2; 42f877f59c 2012-12-21 kinaba: int R = 2; 42f877f59c 2012-12-21 kinaba: long long _ = 0LL; 42f877f59c 2012-12-21 kinaba: END 42f877f59c 2012-12-21 kinaba: CASE(6) 42f877f59c 2012-12-21 kinaba: int L = 2; 42f877f59c 2012-12-21 kinaba: int R = 3; 42f877f59c 2012-12-21 kinaba: long long _ = 0LL; 42f877f59c 2012-12-21 kinaba: END 42f877f59c 2012-12-21 kinaba: CASE(6) 42f877f59c 2012-12-21 kinaba: int L = 2; 42f877f59c 2012-12-21 kinaba: int R = 4; 42f877f59c 2012-12-21 kinaba: long long _ = 3LL; 42f877f59c 2012-12-21 kinaba: END 42f877f59c 2012-12-21 kinaba: CASE(6) 42f877f59c 2012-12-21 kinaba: int L = 4; 42f877f59c 2012-12-21 kinaba: int R = 4; 42f877f59c 2012-12-21 kinaba: long long _ = 1LL; 42f877f59c 2012-12-21 kinaba: END 42f877f59c 2012-12-21 kinaba: 42f877f59c 2012-12-21 kinaba: } 42f877f59c 2012-12-21 kinaba: // END CUT HERE