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<set>
  19. #include<queue>
  20. #include<cctype>
  21. using namespace std;
  22. #define pb push_back
  23. #define all(s) s.begin(),s.end()
  24. #define f(i,a,b) for(int i=a;i<b;i++)
  25. #define F(i,a,b) for(int i=a;i>=b;i--)
  26. #define PI 3.1415926535897932384626433832795
  27. #define INF 2000000000
  28. #define BIG_INF 7000000000000000000LL
  29. #define mp make_pair
  30. #define eps 1e-9
  31. #define LL long long
  32. #define si(n) scanf("%d",&n)
  33. #define sll(n) scanf("%lld",&n)
  34. #define mod 1000000007
  35. #define mm 10000000
  36.  
  37. string inttostring(int n)
  38. {
  39.     stringstream a;
  40.     a<<n;
  41.     return a.str();
  42. }
  43.  
  44. int stringtoint(string A)
  45. {
  46.     istringstream a(A);
  47.     int p;
  48.     a>>p;
  49.     return p;
  50. }
  51.  
  52. //////////////////////////////////////////////////////
  53.  
  54. class GeometricProgressions {
  55. public:
  56.     int fac(LL num,set<int>& S)
  57.     {
  58.         for(LL c=2;c*c<=num;c++)
  59.         {
  60.             if(num%c==0)
  61.             {
  62.                 S.insert(c);
  63.                 while(num%c==0) num/=c;
  64.             }
  65.         }
  66.         if(num!=1) S.insert(num);
  67.         return 0;
  68.     }
  69.     int dec(LL num,vector<int>& V, vector<int> A)
  70.     {
  71.         f(i,0,A.size())
  72.         {
  73.             if(num%A[i]==0)
  74.             {
  75.                 int c=0;
  76.                 while(num%A[i]==0)
  77.                 {
  78.                     c++;
  79.                     num/=A[i];
  80.                 }
  81.                 V.pb(c);
  82.             }
  83.             else V.pb(0);
  84.         }
  85.         return 0;
  86.     }
  87.    int count( int b1, int q1, int n1, int b2, int q2, int n2 ) {
  88.     if(b2==0 || q2<=1)
  89.     {
  90.         swap(b1,b2);
  91.         swap(q1,q2);
  92.         swap(n1,n2);
  93.     }
  94.     if(b1==0 || q1<=1)
  95.     {
  96.         set<LL> S;
  97.         S.insert(b1);
  98.         if(n1>1)
  99.         S.insert(b1*q1);
  100.         LL cur=b2;
  101.         f(i,0,n2)
  102.         {
  103.             S.insert(cur);
  104.             cur*=q2;
  105.             if(cur>500000000)
  106.             {
  107.                 return (n2-i-1)+S.size();
  108.             }
  109.         }
  110.         return S.size();
  111.     }
  112.  
  113.     set<int> factors;
  114.     fac(b1,factors);
  115.     fac(q1,factors);
  116.     fac(b2,factors);
  117.     fac(q2,factors);
  118.     vector<int> FF(all(factors));
  119.  
  120.     set<vector<int> > SS;
  121.  
  122.     vector<int> req1,req2,reb1,reb2;
  123.  
  124.     dec(q1,req1,FF);
  125.     dec(q2,req2,FF);
  126.     dec(b1,reb1,FF);
  127.     dec(b2,reb2,FF);
  128.  
  129.     f(i,0,n1)
  130.     {
  131.         SS.insert(reb1);
  132.         f(i,0,reb1.size())
  133.         {
  134.             reb1[i]+=req1[i];
  135.         }
  136.     }
  137.  
  138.     f(i,0,n2)
  139.     {
  140.         SS.insert(reb2);
  141.         f(i,0,reb2.size())
  142.         {
  143.             reb2[i]+=req2[i];
  144.         }
  145.     }
  146.  
  147.     return SS.size();
  148.  
  149.  
  150.    }
  151. };
  152.  
  153. // BEGIN CUT HERE
  154. namespace moj_harness {
  155.     int run_test_case(int);
  156. 	void run_test(int casenum = -1, bool quiet = false) {
  157. 		if (casenum != -1) {
  158. 			if (run_test_case(casenum) == -1 && !quiet) {
  159. 				cerr << "Illegal input! Test case " << casenum << " does not exist." << endl;
  160. 			}
  161. 			return;
  162. 		}
  163.  
  164. 		int correct = 0, total = 0;
  165. 		for (int i=0;; ++i) {
  166. 			int x = run_test_case(i);
  167. 			if (x == -1) {
  168. 				if (i >= 100) break;
  169. 				continue;
  170. 			}
  171. 			correct += x;
  172. 			++total;
  173. 		}
  174.  
  175. 		if (total == 0) {
  176. 			cerr << "No test cases run." << endl;
  177. 		} else if (correct < total) {
  178. 			cerr << "Some cases FAILED (passed " << correct << " of " << total << ")." << endl;
  179. 		} else {
  180. 			cerr << "All " << total << " tests passed!" << endl;
  181. 		}
  182. 	}
  183.  
  184. 	int verify_case(int casenum, const int &expected, const int &received, clock_t elapsed) {
  185. 		cerr << "Example " << casenum << "... ";
  186.  
  187. 		string verdict;
  188. 		vector<string> info;
  189. 		char buf[100];
  190.  
  191. 		if (elapsed > CLOCKS_PER_SEC / 200) {
  192. 			sprintf(buf, "time %.2fs", elapsed * (1.0/CLOCKS_PER_SEC));
  193. 			info.push_back(buf);
  194. 		}
  195.  
  196. 		if (expected == received) {
  197. 			verdict = "PASSED";
  198. 		} else {
  199. 			verdict = "FAILED";
  200. 		}
  201.  
  202. 		cerr << verdict;
  203. 		if (!info.empty()) {
  204. 			cerr << " (";
  205. 			for (int i=0; i<(int)info.size(); ++i) {
  206. 				if (i > 0) cerr << ", ";
  207. 				cerr << info[i];
  208. 			}
  209. 			cerr << ")";
  210. 		}
  211. 		cerr << endl;
  212.  
  213. 		if (verdict == "FAILED") {
  214. 			cerr << "    Expected: " << expected << endl;
  215. 			cerr << "    Received: " << received << endl;
  216. 		}
  217.  
  218. 		return verdict == "PASSED";
  219. 	}
  220.  
  221. 	int run_test_case(int casenum__) {
  222. 		switch (casenum__) {
  223. 		case 0: {
  224. 			int b1                    = 3;
  225. 			int q1                    = 2;
  226. 			int n1                    = 5;
  227. 			int b2                    = 6;
  228. 			int q2                    = 2;
  229. 			int n2                    = 5;
  230. 			int expected__            = 6;
  231.  
  232. 			clock_t start__           = clock();
  233. 			int received__            = GeometricProgressions().count(b1, q1, n1, b2, q2, n2);
  234. 			return verify_case(casenum__, expected__, received__, clock()-start__);
  235. 		}
  236. 		case 1: {
  237. 			int b1                    = 3;
  238. 			int q1                    = 2;
  239. 			int n1                    = 5;
  240. 			int b2                    = 2;
  241. 			int q2                    = 3;
  242. 			int n2                    = 5;
  243. 			int expected__            = 9;
  244.  
  245. 			clock_t start__           = clock();
  246. 			int received__            = GeometricProgressions().count(b1, q1, n1, b2, q2, n2);
  247. 			return verify_case(casenum__, expected__, received__, clock()-start__);
  248. 		}
  249. 		case 2: {
  250. 			int b1                    = 1;
  251. 			int q1                    = 1;
  252. 			int n1                    = 1;
  253. 			int b2                    = 0;
  254. 			int q2                    = 0;
  255. 			int n2                    = 1;
  256. 			int expected__            = 2;
  257.  
  258. 			clock_t start__           = clock();
  259. 			int received__            = GeometricProgressions().count(b1, q1, n1, b2, q2, n2);
  260. 			return verify_case(casenum__, expected__, received__, clock()-start__);
  261. 		}
  262. 		case 3: {
  263. 			int b1                    = 3;
  264. 			int q1                    = 4;
  265. 			int n1                    = 100500;
  266. 			int b2                    = 48;
  267. 			int q2                    = 1024;
  268. 			int n2                    = 1000;
  269. 			int expected__            = 100500;
  270.  
  271. 			clock_t start__           = clock();
  272. 			int received__            = GeometricProgressions().count(b1, q1, n1, b2, q2, n2);
  273. 			return verify_case(casenum__, expected__, received__, clock()-start__);
  274. 		}
  275.  
  276. 		// custom cases
  277.  
  278. /*      case 4: {
  279. 			int b1                    = ;
  280. 			int q1                    = ;
  281. 			int n1                    = ;
  282. 			int b2                    = ;
  283. 			int q2                    = ;
  284. 			int n2                    = ;
  285. 			int expected__            = ;
  286.  
  287. 			clock_t start__           = clock();
  288. 			int received__            = GeometricProgressions().count(b1, q1, n1, b2, q2, n2);
  289. 			return verify_case(casenum__, expected__, received__, clock()-start__);
  290. 		}*/
  291. /*      case 5: {
  292. 			int b1                    = ;
  293. 			int q1                    = ;
  294. 			int n1                    = ;
  295. 			int b2                    = ;
  296. 			int q2                    = ;
  297. 			int n2                    = ;
  298. 			int expected__            = ;
  299.  
  300. 			clock_t start__           = clock();
  301. 			int received__            = GeometricProgressions().count(b1, q1, n1, b2, q2, n2);
  302. 			return verify_case(casenum__, expected__, received__, clock()-start__);
  303. 		}*/
  304. /*      case 6: {
  305. 			int b1                    = ;
  306. 			int q1                    = ;
  307. 			int n1                    = ;
  308. 			int b2                    = ;
  309. 			int q2                    = ;
  310. 			int n2                    = ;
  311. 			int expected__            = ;
  312.  
  313. 			clock_t start__           = clock();
  314. 			int received__            = GeometricProgressions().count(b1, q1, n1, b2, q2, n2);
  315. 			return verify_case(casenum__, expected__, received__, clock()-start__);
  316. 		}*/
  317. 		default:
  318. 			return -1;
  319. 		}
  320. 	}
  321. }
  322.  
  323.  
  324. int main(int argc, char *argv[]) {
  325. 	if (argc == 1) {
  326. 		moj_harness::run_test();
  327. 	} else {
  328. 		for (int i=1; i<argc; ++i)
  329. 			moj_harness::run_test(atoi(argv[i]));
  330. 	}
  331. }
  332. // END CUT HERE
  333.  
Success #stdin #stdout 0.07s 7664KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/kpnXRF
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!