Sreekar_0125

Untitled

Aug 20th, 2023
946
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 7.40 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. // #define cerr if(false)cerr
  4. #define int long long
  5. #define pb push_back
  6. #define F first
  7. #define S second
  8. #define yes cout << "Yes\n"
  9. #define no cout << "No\n"
  10. #define yn(x) x ? yes : no
  11. #define f(i, s, e) for (int i = s; i < e; i++)
  12. #define traverse(i, a) for (auto i : a)
  13. #define set_bits(x) __builtin_popcountll(x)
  14. #define leading_zero(x) __builtin_clz(x)
  15. #define trailing_zero(x) __builtin_ctz(x)
  16. #define vi vector<int>
  17. #define vb vector<bool>
  18. #define pii pair<int, int>
  19. #define vpi vector<pii>
  20. #define umi unordered_map<int, int>
  21. #define mi map<int, int>
  22. #define si set<int>
  23. #define sc set<char>
  24. #define maxheap priority_queue<int>
  25. #define minheap priority_queue<int, vector<int>, greater<int>>
  26. #define all(x) x.begin(), x.end()
  27. #define minele(x) *min_element(all(x))
  28. #define maxele(x) *max_element(all(x))
  29. #define MOD 1000000007
  30. #define endl '\n'
  31.  
  32. #ifndef ONLINE_JUDGE
  33. #define debug(x)            \
  34.     cerr << (#x) << " is "; \
  35.     _print(x)
  36. #define dbg(x) \
  37.     cerr << (#x) << " is " << x << endl;
  38. #else
  39. #define debug(x)
  40. #define dbg(x)
  41. #endif
  42.  
  43. const int N = 1e6;
  44.  
  45. template <typename T>
  46. void _print(T a)
  47. {
  48.     cerr << a;
  49. }
  50. template <typename T>
  51. void print(T a)
  52. {
  53.     cout << a << ' ';
  54. }
  55. template <typename T>
  56. void println(T a)
  57. {
  58.     cout << a << endl;
  59. }
  60.  
  61. template <typename T>
  62. void input(vector<T> &v)
  63. {
  64.     f(i, 0, (int)v.size()) cin >> v[i];
  65. }
  66.  
  67. template <typename T>
  68. void input(T &a)
  69. {
  70.     cin >> a;
  71. }
  72.  
  73. template <typename T>
  74. void print(vector<T> &v)
  75. {
  76.     f(i, 0, (int)v.size()) cout << v[i] << ' ';
  77.     cout << endl;
  78. }
  79.  
  80. template <class T, class V>
  81. void _print(pair<T, V> p);
  82. template <class T>
  83. void _print(vector<T> v);
  84. template <class T>
  85. void _print(set<T> v);
  86. template <class T, class V>
  87. void _print(map<T, V> v);
  88. template <class T>
  89. void _print(multiset<T> v);
  90. template <class T, class V>
  91. void _print(pair<T, V> p)
  92. {
  93.     cerr << "{";
  94.     _print(p.F);
  95.     cerr << ",";
  96.     _print(p.S);
  97.     cerr << "} ";
  98. }
  99. template <class T>
  100. void _print(vector<T> v)
  101. {
  102.     cerr << "[ ";
  103.     for (T i : v)
  104.     {
  105.         _print(i);
  106.         cerr << " ";
  107.     }
  108.     cerr << "]";
  109.     cerr << endl;
  110. }
  111. template <class T>
  112. void _print(set<T> v)
  113. {
  114.     cerr << "[ ";
  115.     for (T i : v)
  116.     {
  117.         _print(i);
  118.         cerr << " ";
  119.     }
  120.     cerr << "]";
  121.     cerr << endl;
  122. }
  123. template <class T>
  124. void _print(multiset<T> v)
  125. {
  126.     cerr << "[ ";
  127.     for (T i : v)
  128.     {
  129.         _print(i);
  130.         cerr << " ";
  131.     }
  132.     cerr << "]";
  133.     cerr << endl;
  134. }
  135. template <class T, class V>
  136. void _print(map<T, V> v)
  137. {
  138.     cerr << "[ ";
  139.     for (auto i : v)
  140.     {
  141.         _print(i);
  142.         cerr << " ";
  143.     }
  144.     cerr << "]";
  145.     cerr << endl;
  146. }
  147. template <class T, class V>
  148. void _print(unordered_map<T, V> v)
  149. {
  150.     cerr << "[ ";
  151.     for (auto i : v)
  152.     {
  153.         _print(i);
  154.         cerr << " ";
  155.     }
  156.     cerr << "]";
  157.     cerr << endl;
  158. }
  159.  
  160. /////////////Sieve///////////////
  161. vb sieve(N + 5, true);
  162. vi primes;
  163. void gensieve()
  164. {
  165.     sieve[0] = sieve[1] = false;
  166.     for (int i = 2; i <= sqrt(N); i++)
  167.     {
  168.         if (sieve[i])
  169.         {
  170.             for (int j = i * i; j <= N; j += i)
  171.                 sieve[j] = false;
  172.         }
  173.     }
  174.     for (int i = 2; i <= N; i++)
  175.     {
  176.         if (sieve[i])
  177.             primes.pb(i);
  178.     }
  179. }
  180. ////////////////////////////////
  181.  
  182. int binpow(int a, int b, int m)
  183. {
  184.     a %= m;
  185.     int ans = 1;
  186.     while (b > 0)
  187.     {
  188.         if (b & 1)
  189.         {
  190.             ans = (ans * a) % MOD;
  191.         }
  192.         a = (a * a) % MOD;
  193.         b >>= 1;
  194.     }
  195.     return ans;
  196. }
  197.  
  198. int modadd(int a, int b)
  199. {
  200.     return (a % MOD + b % MOD) % MOD;
  201. }
  202. int modsub(int a, int b)
  203. {
  204.     return ((a % MOD - b % MOD) % MOD + MOD) % MOD;
  205. }
  206. int modmul(int a, int b)
  207. {
  208.     return (a % MOD * b % MOD) % MOD;
  209. }
  210. int moddiv(int a, int b)
  211. {
  212.     return ((a % MOD) * (binpow(b, MOD - 2, MOD))) % MOD;
  213. }
  214.  
  215. int lbnd(vi &v, int x)
  216. {
  217.     int n = v.size();
  218.     int low = 0;
  219.     int high = n - 1;
  220.     int ans = -1;
  221.     while (low <= high)
  222.     {
  223.         int mid = (low + high) >> 1;
  224.         if (v[mid] <= x)
  225.         {
  226.             ans = mid;
  227.             low = mid + 1;
  228.         }
  229.         else
  230.         {
  231.             high = mid - 1;
  232.         }
  233.     }
  234.     return ans;
  235. }
  236.  
  237. int ubnd(vi &v, int x)
  238. {
  239.     int n = v.size();
  240.     int low = 0;
  241.     int high = n - 1;
  242.     int ans = -1;
  243.     while (low <= high)
  244.     {
  245.         int mid = (low + high) >> 1;
  246.         if (v[mid] >= x)
  247.         {
  248.             ans = mid;
  249.             high = mid - 1;
  250.         }
  251.         else
  252.         {
  253.             low = mid + 1;
  254.         }
  255.     }
  256.     return ans;
  257. }
  258.  
  259. // vpi moves = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
  260. // vi graph[N + 1];
  261. // vb visited(N + 1, false);
  262. // vi parent(N + 1, -1);
  263. // vi level(N + 1, 0);
  264.  
  265. // void bfs(vi *graph, vb &visited, vi &parent, vi &level, int start)
  266. // {
  267. //     queue<int> q;
  268. //     visited[start] = true;
  269. //     q.push(start);
  270. //     while (!q.empty())
  271. //     {
  272. //         int node = q.front();
  273. //         traverse(i, graph[node])
  274. //         {
  275. //             if (!visited[i])
  276. //             {
  277. //                 if (parent[i] == -1)
  278. //                     parent[i] = node;
  279. //                 if (level[i] == 0)
  280. //                     level[i] = 1 + level[node];
  281. //                 visited[i] = true;
  282. //                 q.push(i);
  283. //             }
  284. //         }
  285. //         q.pop();
  286. //     }
  287. // }
  288.  
  289. // void dfs(vi *graph, vb &visited, int start)
  290. // {
  291. //     visited[start] = true;
  292. //     traverse(i, graph[start])
  293. //     {
  294. //         if (!visited[i])
  295. //         {
  296. //             visited[i] = true;
  297. //             dfs(graph, visited, i);
  298. //         }
  299. //     }
  300. // }
  301.  
  302. void fast()
  303. {
  304.     ios_base::sync_with_stdio(false);
  305.     cin.tie(NULL);
  306.     cout.tie(NULL);
  307. }
  308.  
  309. void init_code()
  310. {
  311. #ifndef ONLINE_JUDGE
  312.     freopen("input.txt", "r", stdin);
  313.     freopen("output.txt", "w", stdout);
  314.     freopen("error.txt", "w", stderr);
  315. #endif // ONLINE_JUDGE
  316. }
  317.  
  318. void solve()
  319. {
  320.     int n;
  321.     cin >> n;
  322.  
  323.     vi v(n);
  324.     input(v);
  325.  
  326.     vi prefix = v;
  327.     vi suffix = v;
  328.  
  329.     reverse(all(suffix));
  330.  
  331.     f(i, 1, n)
  332.     {
  333.         prefix[i] = __gcd(prefix[i - 1], prefix[i]);
  334.         suffix[i] = __gcd(suffix[i - 1], suffix[i]);
  335.     }
  336.  
  337.     reverse(all(suffix));
  338.     debug(prefix);
  339.     debug(suffix);
  340.  
  341.     vi nums;
  342.     nums.pb(suffix[1]);
  343.  
  344.     for (int i = 1; i <= n - 2; i++)
  345.     {
  346.         int x = __gcd(prefix[i - 1], suffix[i + 1]);
  347.         nums.pb(x);
  348.     }
  349.  
  350.     nums.pb(prefix[n - 2]);
  351.  
  352.     debug(nums);
  353.     int mini = LLONG_MAX;
  354.  
  355.     f(i, 0, n)
  356.     {
  357.         if (sieve[nums[i]])
  358.         {
  359.             mini = min(mini, 1LL);
  360.             break;
  361.         }
  362.  
  363.         int cnt = 0;
  364.  
  365.         int x = nums[i];
  366.         int limit = sqrt(x);
  367.  
  368.         for (auto p : primes)
  369.         {
  370.             if (p > limit)
  371.                 break;
  372.             while (x % p == 0)
  373.             {
  374.                 x /= p;
  375.                 cnt++;
  376.             }
  377.         }
  378.  
  379.         if (x != 1)
  380.         {
  381.             cnt++;
  382.         }
  383.  
  384.         mini = min(mini, cnt);
  385.     }
  386.     dbg(mini);
  387.     if (mini >= 2)
  388.         println("BOB");
  389.     else
  390.         println("DRAW");
  391. }
  392.  
  393. signed main()
  394. {
  395.     init_code();
  396.     fast();
  397.     int t = 1;
  398.     cin >> t;
  399.     gensieve();
  400.     while (t--)
  401.     {
  402.         solve();
  403.     }
  404.     return 0;
  405. }
  406.  
Advertisement
Add Comment
Please, Sign In to add comment