fork download
copy 
  1. /*
  2. written by- Piyush Golani
  3. language- c++
  4. country- India
  5. College- N.I.T Jamshedpur
  6. */
  7. #include <cmath>
  8. #include <ctime>
  9. #include <iostream>
  10. #include <string>
  11. #include <vector>
  12. #include<cstdio>
  13. #include<sstream>
  14. #include<algorithm>
  15. #include<cstdlib>
  16. #include<cstring>
  17. #include<map>
  18. #include<queue>
  19. #include<cctype>
  20. using namespace std;
  21. #define pb push_back
  22. #define all(s) s.begin(),s.end()
  23. #define f(i,a,b) for(int i=a;i<b;i++)
  24. #define F(i,a,b) for(int i=a;i>=b;i--)
  25. #define PI 3.1415926535897932384626433832795
  26. #define INF 2000000000
  27. #define BIG_INF 7000000000000000000LL
  28. #define mp make_pair
  29. #define eps 1e-9
  30. #define LL long long
  31. #define si(n) scanf("%d",&n)
  32. #define sll(n) scanf("%lld",&n)
  33. #define mod 1000000007
  34. #define mm 10000000
  35.  
  36. string inttostring(int n)
  37. {
  38.     stringstream a;
  39.     a<<n;
  40.     return a.str();
  41. }
  42.  
  43. int stringtoint(string A)
  44. {
  45.     istringstream a(A);
  46.     int p;
  47.     a>>p;
  48.     return p;
  49. }
  50.  
  51. ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
  52.  
  53. class TheDivisionGame {
  54. public:
  55.    long long countWinningIntervals( int L, int R ) {
  56.     int n=R-L+1;
  57.     int cur[n],nim[n];
  58.     memset(nim,0,sizeof(nim));
  59.     f(i,L,R+1)
  60.     {
  61.         cur[i-L]=i;
  62.     }
  63.     for(int i=2;i*i<=R;i++)
  64.     {
  65.         int s=L;
  66.         if(L%i!=0)
  67.         s+=i-(s%i);
  68.         while(s<=R)
  69.         {
  70.             while(cur[s-L]%i==0)
  71.             {
  72.                 cur[s-L]/=i;
  73.                 nim[s-L]++;
  74.             }
  75.             s+=i;
  76.         }
  77.     }
  78.     f(i,0,n)
  79.     {
  80.         if(cur[i]>1) nim[i]++;
  81.     }
  82.     LL dp[32][2]={0},res=0;
  83.     for(int i=n-1;i>=0;i--)
  84.     {
  85.         f(x,0,32)
  86.         {
  87.             dp[x^nim[i]][i%2]=dp[x][!(i%2)];
  88.         }
  89.         dp[nim[i]][i%2]++;
  90.         res+=dp[0][i%2];
  91.     }
  92.     return ((LL)n*(n+1))/2-res;
  93.    }
  94. };
  95.  
  96. // BEGIN CUT HERE
  97. namespace moj_harness {
  98.     int run_test_case(int);
  99. 	void run_test(int casenum = -1, bool quiet = false) {
  100. 		if (casenum != -1) {
  101. 			if (run_test_case(casenum) == -1 && !quiet) {
  102. 				cerr << "Illegal input! Test case " << casenum << " does not exist." << endl;
  103. 			}
  104. 			return;
  105. 		}
  106.  
  107. 		int correct = 0, total = 0;
  108. 		for (int i=0;; ++i) {
  109. 			int x = run_test_case(i);
  110. 			if (x == -1) {
  111. 				if (i >= 100) break;
  112. 				continue;
  113. 			}
  114. 			correct += x;
  115. 			++total;
  116. 		}
  117.  
  118. 		if (total == 0) {
  119. 			cerr << "No test cases run." << endl;
  120. 		} else if (correct < total) {
  121. 			cerr << "Some cases FAILED (passed " << correct << " of " << total << ")." << endl;
  122. 		} else {
  123. 			cerr << "All " << total << " tests passed!" << endl;
  124. 		}
  125. 	}
  126.  
  127. 	int verify_case(int casenum, const long long &expected, const long long &received, clock_t elapsed) {
  128. 		cerr << "Example " << casenum << "... ";
  129.  
  130. 		string verdict;
  131. 		vector<string> info;
  132. 		char buf[100];
  133.  
  134. 		if (elapsed > CLOCKS_PER_SEC / 200) {
  135. 			sprintf(buf, "time %.2fs", elapsed * (1.0/CLOCKS_PER_SEC));
  136. 			info.push_back(buf);
  137. 		}
  138.  
  139. 		if (expected == received) {
  140. 			verdict = "PASSED";
  141. 		} else {
  142. 			verdict = "FAILED";
  143. 		}
  144.  
  145. 		cerr << verdict;
  146. 		if (!info.empty()) {
  147. 			cerr << " (";
  148. 			for (int i=0; i<(int)info.size(); ++i) {
  149. 				if (i > 0) cerr << ", ";
  150. 				cerr << info[i];
  151. 			}
  152. 			cerr << ")";
  153. 		}
  154. 		cerr << endl;
  155.  
  156. 		if (verdict == "FAILED") {
  157. 			cerr << "    Expected: " << expected << endl;
  158. 			cerr << "    Received: " << received << endl;
  159. 		}
  160.  
  161. 		return verdict == "PASSED";
  162. 	}
  163.  
  164. 	int run_test_case(int casenum__) {
  165. 		switch (casenum__) {
  166. 		case 0: {
  167. 			int L                     = 9;
  168. 			int R                     = 10;
  169. 			long long expected__      = 2;
  170.  
  171. 			clock_t start__           = clock();
  172. 			long long received__      = TheDivisionGame().countWinningIntervals(L, R);
  173. 			return verify_case(casenum__, expected__, received__, clock()-start__);
  174. 		}
  175. 		case 1: {
  176. 			int L                     = 2;
  177. 			int R                     = 5;
  178. 			long long expected__      = 9;
  179.  
  180. 			clock_t start__           = clock();
  181. 			long long received__      = TheDivisionGame().countWinningIntervals(L, R);
  182. 			return verify_case(casenum__, expected__, received__, clock()-start__);
  183. 		}
  184. 		case 2: {
  185. 			int L                     = 2;
  186. 			int R                     = 6;
  187. 			long long expected__      = 13;
  188.  
  189. 			clock_t start__           = clock();
  190. 			long long received__      = TheDivisionGame().countWinningIntervals(L, R);
  191. 			return verify_case(casenum__, expected__, received__, clock()-start__);
  192. 		}
  193. 		case 3: {
  194. 			int L                     = 2;
  195. 			int R                     = 100;
  196. 			long long expected__      = 4345;
  197.  
  198. 			clock_t start__           = clock();
  199. 			long long received__      = TheDivisionGame().countWinningIntervals(L, R);
  200. 			return verify_case(casenum__, expected__, received__, clock()-start__);
  201. 		}
  202. 		case 4: {
  203. 			int L                     = 12566125;
  204. 			int R                     = 12567777;
  205. 			long long expected__      = 1313432;
  206.  
  207. 			clock_t start__           = clock();
  208. 			long long received__      = TheDivisionGame().countWinningIntervals(L, R);
  209. 			return verify_case(casenum__, expected__, received__, clock()-start__);
  210. 		}
  211.  
  212. 		// custom cases
  213.  
  214. /*      case 5: {
  215. 			int L                     = ;
  216. 			int R                     = ;
  217. 			long long expected__      = ;
  218.  
  219. 			clock_t start__           = clock();
  220. 			long long received__      = TheDivisionGame().countWinningIntervals(L, R);
  221. 			return verify_case(casenum__, expected__, received__, clock()-start__);
  222. 		}*/
  223. /*      case 6: {
  224. 			int L                     = ;
  225. 			int R                     = ;
  226. 			long long expected__      = ;
  227.  
  228. 			clock_t start__           = clock();
  229. 			long long received__      = TheDivisionGame().countWinningIntervals(L, R);
  230. 			return verify_case(casenum__, expected__, received__, clock()-start__);
  231. 		}*/
  232. /*      case 7: {
  233. 			int L                     = ;
  234. 			int R                     = ;
  235. 			long long expected__      = ;
  236.  
  237. 			clock_t start__           = clock();
  238. 			long long received__      = TheDivisionGame().countWinningIntervals(L, R);
  239. 			return verify_case(casenum__, expected__, received__, clock()-start__);
  240. 		}*/
  241. 		default:
  242. 			return -1;
  243. 		}
  244. 	}
  245. }
  246.  
  247.  
  248. int main(int argc, char *argv[]) {
  249. 	if (argc == 1) {
  250. 		moj_harness::run_test();
  251. 	} else {
  252. 		for (int i=1; i<argc; ++i)
  253. 			moj_harness::run_test(atoi(argv[i]));
  254. 	}
  255. }
  256. // END CUT HERE
  257.  
Success #stdin #stdout 0.02s 2820KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/ubRpJX
language:
C++ (gcc 8.3)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!