Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- // #define cerr if(false)cerr
- #define int long long
- #define pb push_back
- #define F first
- #define S second
- #define yes cout << "Yes\n"
- #define no cout << "No\n"
- #define yn(x) x ? yes : no
- #define f(i, s, e) for (int i = s; i < e; i++)
- #define traverse(i, a) for (auto i : a)
- #define set_bits(x) __builtin_popcountll(x)
- #define leading_zero(x) __builtin_clz(x)
- #define trailing_zero(x) __builtin_ctz(x)
- #define vi vector<int>
- #define vb vector<bool>
- #define pii pair<int, int>
- #define vpi vector<pii>
- #define umi unordered_map<int, int>
- #define mi map<int, int>
- #define si set<int>
- #define sc set<char>
- #define maxheap priority_queue<int>
- #define minheap priority_queue<int, vector<int>, greater<int>>
- #define all(x) x.begin(), x.end()
- #define minele(x) *min_element(all(x))
- #define maxele(x) *max_element(all(x))
- #define MOD 1000000007
- #define endl '\n'
- #ifndef ONLINE_JUDGE
- #define debug(x) \
- cerr << (#x) << " is "; \
- _print(x)
- #define dbg(x) \
- cerr << (#x) << " is " << x << endl;
- #else
- #define debug(x)
- #define dbg(x)
- #endif
- const int N = 1e6;
- template <typename T>
- void _print(T a)
- {
- cerr << a;
- }
- template <typename T>
- void print(T a)
- {
- cout << a << ' ';
- }
- template <typename T>
- void println(T a)
- {
- cout << a << endl;
- }
- template <typename T>
- void input(vector<T> &v)
- {
- f(i, 0, (int)v.size()) cin >> v[i];
- }
- template <typename T>
- void input(T &a)
- {
- cin >> a;
- }
- template <typename T>
- void print(vector<T> &v)
- {
- f(i, 0, (int)v.size()) cout << v[i] << ' ';
- cout << endl;
- }
- template <class T, class V>
- void _print(pair<T, V> p);
- template <class T>
- void _print(vector<T> v);
- template <class T>
- void _print(set<T> v);
- template <class T, class V>
- void _print(map<T, V> v);
- template <class T>
- void _print(multiset<T> v);
- template <class T, class V>
- void _print(pair<T, V> p)
- {
- cerr << "{";
- _print(p.F);
- cerr << ",";
- _print(p.S);
- cerr << "} ";
- }
- template <class T>
- void _print(vector<T> v)
- {
- cerr << "[ ";
- for (T i : v)
- {
- _print(i);
- cerr << " ";
- }
- cerr << "]";
- cerr << endl;
- }
- template <class T>
- void _print(set<T> v)
- {
- cerr << "[ ";
- for (T i : v)
- {
- _print(i);
- cerr << " ";
- }
- cerr << "]";
- cerr << endl;
- }
- template <class T>
- void _print(multiset<T> v)
- {
- cerr << "[ ";
- for (T i : v)
- {
- _print(i);
- cerr << " ";
- }
- cerr << "]";
- cerr << endl;
- }
- template <class T, class V>
- void _print(map<T, V> v)
- {
- cerr << "[ ";
- for (auto i : v)
- {
- _print(i);
- cerr << " ";
- }
- cerr << "]";
- cerr << endl;
- }
- template <class T, class V>
- void _print(unordered_map<T, V> v)
- {
- cerr << "[ ";
- for (auto i : v)
- {
- _print(i);
- cerr << " ";
- }
- cerr << "]";
- cerr << endl;
- }
- /////////////Sieve///////////////
- vb sieve(N + 5, true);
- vi primes;
- void gensieve()
- {
- sieve[0] = sieve[1] = false;
- for (int i = 2; i <= sqrt(N); i++)
- {
- if (sieve[i])
- {
- for (int j = i * i; j <= N; j += i)
- sieve[j] = false;
- }
- }
- for (int i = 2; i <= N; i++)
- {
- if (sieve[i])
- primes.pb(i);
- }
- }
- ////////////////////////////////
- int binpow(int a, int b, int m)
- {
- a %= m;
- int ans = 1;
- while (b > 0)
- {
- if (b & 1)
- {
- ans = (ans * a) % MOD;
- }
- a = (a * a) % MOD;
- b >>= 1;
- }
- return ans;
- }
- int modadd(int a, int b)
- {
- return (a % MOD + b % MOD) % MOD;
- }
- int modsub(int a, int b)
- {
- return ((a % MOD - b % MOD) % MOD + MOD) % MOD;
- }
- int modmul(int a, int b)
- {
- return (a % MOD * b % MOD) % MOD;
- }
- int moddiv(int a, int b)
- {
- return ((a % MOD) * (binpow(b, MOD - 2, MOD))) % MOD;
- }
- int lbnd(vi &v, int x)
- {
- int n = v.size();
- int low = 0;
- int high = n - 1;
- int ans = -1;
- while (low <= high)
- {
- int mid = (low + high) >> 1;
- if (v[mid] <= x)
- {
- ans = mid;
- low = mid + 1;
- }
- else
- {
- high = mid - 1;
- }
- }
- return ans;
- }
- int ubnd(vi &v, int x)
- {
- int n = v.size();
- int low = 0;
- int high = n - 1;
- int ans = -1;
- while (low <= high)
- {
- int mid = (low + high) >> 1;
- if (v[mid] >= x)
- {
- ans = mid;
- high = mid - 1;
- }
- else
- {
- low = mid + 1;
- }
- }
- return ans;
- }
- // vpi moves = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
- // vi graph[N + 1];
- // vb visited(N + 1, false);
- // vi parent(N + 1, -1);
- // vi level(N + 1, 0);
- // void bfs(vi *graph, vb &visited, vi &parent, vi &level, int start)
- // {
- // queue<int> q;
- // visited[start] = true;
- // q.push(start);
- // while (!q.empty())
- // {
- // int node = q.front();
- // traverse(i, graph[node])
- // {
- // if (!visited[i])
- // {
- // if (parent[i] == -1)
- // parent[i] = node;
- // if (level[i] == 0)
- // level[i] = 1 + level[node];
- // visited[i] = true;
- // q.push(i);
- // }
- // }
- // q.pop();
- // }
- // }
- // void dfs(vi *graph, vb &visited, int start)
- // {
- // visited[start] = true;
- // traverse(i, graph[start])
- // {
- // if (!visited[i])
- // {
- // visited[i] = true;
- // dfs(graph, visited, i);
- // }
- // }
- // }
- void fast()
- {
- ios_base::sync_with_stdio(false);
- cin.tie(NULL);
- cout.tie(NULL);
- }
- void init_code()
- {
- #ifndef ONLINE_JUDGE
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- freopen("error.txt", "w", stderr);
- #endif // ONLINE_JUDGE
- }
- void solve()
- {
- int n;
- cin >> n;
- vi v(n);
- input(v);
- vi prefix = v;
- vi suffix = v;
- reverse(all(suffix));
- f(i, 1, n)
- {
- prefix[i] = __gcd(prefix[i - 1], prefix[i]);
- suffix[i] = __gcd(suffix[i - 1], suffix[i]);
- }
- reverse(all(suffix));
- debug(prefix);
- debug(suffix);
- vi nums;
- nums.pb(suffix[1]);
- for(int i = 1; i <= n - 2; i++)
- {
- int x = __gcd(prefix[i - 1], suffix[i + 1]);
- nums.pb(x);
- }
- nums.pb(prefix[n - 2]);
- debug(nums);
- int mini = LLONG_MAX;
- f(i, 0, n)
- {
- if(sieve[nums[i]])
- {
- mini = min(mini, 1LL);
- continue;
- }
- int cnt = 0;
- int x = nums[i];
- int limit = sqrt(x);
- for(auto p: primes)
- {
- if(p > limit) break;
- while(x % p == 0)
- {
- x /= p;
- cnt++;
- }
- }
- mini = min(mini, cnt);
- }
- dbg(mini);
- if(mini >= 2) println("BOB");
- else println("DRAW");
- }
- signed main()
- {
- init_code();
- fast();
- int t = 1;
- cin >> t;
- gensieve();
- while (t--)
- {
- solve();
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment