d3b1273780 2014-06-12 kinaba: #include <iostream> d3b1273780 2014-06-12 kinaba: #include <sstream> d3b1273780 2014-06-12 kinaba: #include <iomanip> d3b1273780 2014-06-12 kinaba: #include <vector> d3b1273780 2014-06-12 kinaba: #include <string> d3b1273780 2014-06-12 kinaba: #include <map> d3b1273780 2014-06-12 kinaba: #include <set> d3b1273780 2014-06-12 kinaba: #include <algorithm> d3b1273780 2014-06-12 kinaba: #include <numeric> d3b1273780 2014-06-12 kinaba: #include <iterator> d3b1273780 2014-06-12 kinaba: #include <functional> d3b1273780 2014-06-12 kinaba: #include <complex> d3b1273780 2014-06-12 kinaba: #include <queue> d3b1273780 2014-06-12 kinaba: #include <stack> d3b1273780 2014-06-12 kinaba: #include <cmath> d3b1273780 2014-06-12 kinaba: #include <cassert> d3b1273780 2014-06-12 kinaba: #include <tuple> d3b1273780 2014-06-12 kinaba: using namespace std; d3b1273780 2014-06-12 kinaba: typedef long long LL; d3b1273780 2014-06-12 kinaba: typedef complex<double> CMP; d3b1273780 2014-06-12 kinaba: d3b1273780 2014-06-12 kinaba: class AlwaysDefined { public: d3b1273780 2014-06-12 kinaba: long long countIntegers(long long L, long long R, int W) d3b1273780 2014-06-12 kinaba: { d3b1273780 2014-06-12 kinaba: vector<vector<int>> tbl(W); d3b1273780 2014-06-12 kinaba: for(int q=1; q<=W-1; ++q) d3b1273780 2014-06-12 kinaba: for(int r=1; r<=W-1; ++r) d3b1273780 2014-06-12 kinaba: if(q*r%W == r) d3b1273780 2014-06-12 kinaba: tbl[q].push_back(r); d3b1273780 2014-06-12 kinaba: d3b1273780 2014-06-12 kinaba: // count all numbers that can be generated by repeating d3b1273780 2014-06-12 kinaba: // x ==> rx where tbl[x%W].has(r) d3b1273780 2014-06-12 kinaba: if(R<=1000000) d3b1273780 2014-06-12 kinaba: { d3b1273780 2014-06-12 kinaba: vector<int> V(R+1, false); d3b1273780 2014-06-12 kinaba: for(int k=0; k*W+1<=R; ++k) d3b1273780 2014-06-12 kinaba: { d3b1273780 2014-06-12 kinaba: queue<int> Q; d3b1273780 2014-06-12 kinaba: if(!V[k*W+1]) d3b1273780 2014-06-12 kinaba: Q.push(k*W+1), V[k*W+1]=true; d3b1273780 2014-06-12 kinaba: while(!Q.empty()) d3b1273780 2014-06-12 kinaba: { d3b1273780 2014-06-12 kinaba: int s = Q.front(); d3b1273780 2014-06-12 kinaba: Q.pop(); d3b1273780 2014-06-12 kinaba: for(int r: tbl[s%W]) { d3b1273780 2014-06-12 kinaba: if(s*r<=R && !V[s*r]) d3b1273780 2014-06-12 kinaba: Q.push(s*r), V[s*r]=true; d3b1273780 2014-06-12 kinaba: } d3b1273780 2014-06-12 kinaba: } d3b1273780 2014-06-12 kinaba: } d3b1273780 2014-06-12 kinaba: LL cnt = 0; d3b1273780 2014-06-12 kinaba: for(LL X=L; X<=R; ++X) d3b1273780 2014-06-12 kinaba: if(V[X]) d3b1273780 2014-06-12 kinaba: ++cnt; d3b1273780 2014-06-12 kinaba: return cnt; d3b1273780 2014-06-12 kinaba: } d3b1273780 2014-06-12 kinaba: d3b1273780 2014-06-12 kinaba: d3b1273780 2014-06-12 kinaba: LL cnt = 0; d3b1273780 2014-06-12 kinaba: for(LL X=L; X<=R; ++X) d3b1273780 2014-06-12 kinaba: { d3b1273780 2014-06-12 kinaba: LL x = X; d3b1273780 2014-06-12 kinaba: for(;;) { d3b1273780 2014-06-12 kinaba: if(x%W==0) d3b1273780 2014-06-12 kinaba: break; d3b1273780 2014-06-12 kinaba: if(x%W==1) d3b1273780 2014-06-12 kinaba: {++cnt; break;} d3b1273780 2014-06-12 kinaba: if(x%(x%W)!=0) d3b1273780 2014-06-12 kinaba: break; d3b1273780 2014-06-12 kinaba: x /= x%W; d3b1273780 2014-06-12 kinaba: } d3b1273780 2014-06-12 kinaba: } d3b1273780 2014-06-12 kinaba: return cnt; d3b1273780 2014-06-12 kinaba: } d3b1273780 2014-06-12 kinaba: }; d3b1273780 2014-06-12 kinaba: d3b1273780 2014-06-12 kinaba: // BEGIN CUT HERE d3b1273780 2014-06-12 kinaba: #include <ctime> d3b1273780 2014-06-12 kinaba: double start_time; string timer() d3b1273780 2014-06-12 kinaba: { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } d3b1273780 2014-06-12 kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) d3b1273780 2014-06-12 kinaba: { os << "{ "; d3b1273780 2014-06-12 kinaba: for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) d3b1273780 2014-06-12 kinaba: os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } d3b1273780 2014-06-12 kinaba: void verify_case(const long long& Expected, const long long& Received) { d3b1273780 2014-06-12 kinaba: bool ok = (Expected == Received); d3b1273780 2014-06-12 kinaba: if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; d3b1273780 2014-06-12 kinaba: cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } d3b1273780 2014-06-12 kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); d3b1273780 2014-06-12 kinaba: #define END verify_case(_, AlwaysDefined().countIntegers(L, R, W));} d3b1273780 2014-06-12 kinaba: int main(){ d3b1273780 2014-06-12 kinaba: d3b1273780 2014-06-12 kinaba: CASE(0) d3b1273780 2014-06-12 kinaba: long long L = 10LL; d3b1273780 2014-06-12 kinaba: long long R = 10LL; d3b1273780 2014-06-12 kinaba: int W = 4; d3b1273780 2014-06-12 kinaba: long long _ = 1LL; d3b1273780 2014-06-12 kinaba: END d3b1273780 2014-06-12 kinaba: CASE(1) d3b1273780 2014-06-12 kinaba: long long L = 1LL; d3b1273780 2014-06-12 kinaba: long long R = 99LL; d3b1273780 2014-06-12 kinaba: int W = 2; d3b1273780 2014-06-12 kinaba: long long _ = 50LL; d3b1273780 2014-06-12 kinaba: END d3b1273780 2014-06-12 kinaba: CASE(2) d3b1273780 2014-06-12 kinaba: long long L = 1282LL; d3b1273780 2014-06-12 kinaba: long long R = 1410LL; d3b1273780 2014-06-12 kinaba: int W = 10; d3b1273780 2014-06-12 kinaba: long long _ = 42LL; d3b1273780 2014-06-12 kinaba: END d3b1273780 2014-06-12 kinaba: CASE(178116) d3b1273780 2014-06-12 kinaba: long long L = 1LL; d3b1273780 2014-06-12 kinaba: long long R = 1000000LL; d3b1273780 2014-06-12 kinaba: int W = 30; d3b1273780 2014-06-12 kinaba: long long _ = 154161LL; d3b1273780 2014-06-12 kinaba: END d3b1273780 2014-06-12 kinaba: CASE(3) d3b1273780 2014-06-12 kinaba: long long L = 29195807LL; d3b1273780 2014-06-12 kinaba: long long R = 273209804877LL; d3b1273780 2014-06-12 kinaba: int W = 42; d3b1273780 2014-06-12 kinaba: long long _ = 31415926535LL; d3b1273780 2014-06-12 kinaba: END d3b1273780 2014-06-12 kinaba: CASE(4) d3b1273780 2014-06-12 kinaba: long long L = 1LL; d3b1273780 2014-06-12 kinaba: long long R = 1000000000000000000LL; d3b1273780 2014-06-12 kinaba: int W = 3000; d3b1273780 2014-06-12 kinaba: long long _ = -1LL; d3b1273780 2014-06-12 kinaba: END d3b1273780 2014-06-12 kinaba: CASE(5) d3b1273780 2014-06-12 kinaba: long long L = 1LL; d3b1273780 2014-06-12 kinaba: long long R = 1000000000000000000LL; d3b1273780 2014-06-12 kinaba: int W = 3; d3b1273780 2014-06-12 kinaba: long long _ = -1LL; d3b1273780 2014-06-12 kinaba: END d3b1273780 2014-06-12 kinaba: } d3b1273780 2014-06-12 kinaba: // END CUT HERE