You are given an array of $$$n$$$ positive integers. Insert a minimum non-negative number $$$x \neq 1$$$ in the array, such that the greatest common divisor of all the $$$n + 1$$$ elements becomes $$$1$$$.
The first line consists a number $$$t$$$ which shows the number of testcases.
$$$$$$1 \le t \le 10^4$$$$$$
In the first line of each testcase you'll be given an integer $$$n$$$ which shows the length of the array.
$$$$$$1 \le n \le 10^5$$$$$$
In the second line you'll receive $$$n$$$ positive integers.
$$$$$$1 \le a_i \le 10^{18}$$$$$$
It is guaranteed that sum of $$$n$$$ overall testcases does not exceed $$$10^5$$$.
Print the minimum non-negative integer $$$x \neq 1$$$ such that after insertion the gcd of all the elements of the array becomes $$$1$$$.
2321 14 49333 3 11
2 0
Akbar wants to send $$$n$$$ letters to $$$m$$$ companies.
First letter should be sent to $$$l_{1}{th}$$$ company, second letter should be sent to $$$l_{2}{th}$$$ company, ..... , $$$n_{th}$$$ letter should be sent to $$$l_{n}{th}$$$ company, in the other words, letter $$$i$$$ should be sent to $$$l_{i}{th}$$$ company, $$$(1 \le l_i \le m)$$$.
Akbar bought $$$n$$$ envelopes for sending these letters, and wrote the address of the $$$l_{i}{th}$$$ company on the $$$i_{th}$$$ letter.
Akbar tells Amir to put the $$$i_{th}$$$ letter in the $$$i_{th}$$$ envelope, But Amir wants to not carry out this order properly and ruin the work fundamentally. For this reason, he decided to put the letters in the envelopes in such a way that each envelope contains exactly one letter, but no company receives its own letter.
Now your task is to help Amir to check whether it is possible to do such a thing or not.
In the first line of input, you'll be given two positive integers $$$n$$$ and $$$m$$$.
$$$$$$1 \le m \le n \le 10^5$$$$$$
In the second line of input, you'll be given $$$n$$$ positive integers $$$l_1, l_2, ... , l_n$$$ separated by space, that $$$l_i$$$ shows the destination company of the $$$i_{th}$$$ letter.
$$$$$$1 \le l_i \le m$$$$$$
It's guaranteed that all numbers $$$1, 2, 3, .... , m$$$ have appeared at least once in this sequence.
If it is possible to put the letters in the envelopes so that no letter reaches the corresponding company, print "YES", otherwise print "NO".
3 1 1 1 1
NO
4 4 4 1 2 3
YES
Explanation of testcase $$$1$$$ :
All the letters are addressed to company $$$1$$$, so all the envelopes have the address of company $$$1$$$, so any permutation of the letters in the envelopes, all the letters will reach company $$$1$$$, and Amir will not reach his goal.
Explanation of testcase $$$2$$$ :
We have four letters for companies $$$1, 2, 3, 4$$$ and four envelopes with the addresses of companies $$$1, 2, 3, 4$$$. We put the letter of company $$$1$$$ in the envelope of company $$$2$$$ and the letter of company $$$2$$$ in the envelope of company $$$1$$$. Also, we put the letter of company $$$3$$$ in the envelope of company $$$4$$$ and the letter of company $$$4$$$ in the envelope of company $$$3$$$. In this way, no letter reaches the relevant company and Amir reaches his goal.
You are given an array $$$a$$$ of $$$n$$$ integers, we call a subarray good if its product has an odd number of divisors.
In other words, subarray $$$a[l...r]$$$ $$$(1 \leq l \leq r \leq n)$$$ is good iff $$$(\prod_{i = l}^{r}a_i)$$$ has an odd number of divisors.
You're asked to count the number of good subarrays in the array $$$a$$$.
The first line contains one integer $$$t$$$ $$$(1 \leq t \leq 100)$$$ – the number of test cases.
Each test case has two lines, the first being one integer $$$n$$$ $$$(1 \leq n \leq 2\times10^5)$$$ – the length of the array.
The second line of the test cases is $$$n$$$ integers $$$a_1, a_2, ..., a_n$$$ $$$(1 \leq a_i \leq 300)$$$ – the elements of the array.
It's guaranteed that the sum of $$$n$$$ over all test cases won't exceed $$$10^6$$$.
Print one integer for each test case, the number of good subarrays in the array.
241 2 4 231 1 1
4 6
You are going to host an Age of Empires tournament, and you want it to be perfect.
There are $$$n$$$ players participating, you let your friends organize the seating of the players and now on the $$$i$$$-th seat from the left sits a player with a rating $$$a_i$$$.
After you thought everything was going perfect, it turns out that you only had cables with length $$$k$$$ that means player $$$i$$$ can play with player $$$j$$$ iff ($$$|j - i| \leq k$$$), and if that wasn't bad enough all the players are elitist, so the player $$$i$$$ will play with player $$$j$$$ iff $$$a_i$$$ and $$$a_j$$$ are coprime.
Given the seating of the $$$n$$$ players and length of the cable $$$k$$$ what is the maximum number of matches can you set up. Note that each player can only participate in one match.
The first line contains two integers $$$n$$$ and $$$k$$$ $$$(1 \leq n \leq 10^5; 1 \leq k \leq 8)$$$ – the number of players and the length of the cable.
The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ $$$(1 \leq a_i \leq 10^9)$$$ – the ratings of the players.
Print a single integer, the answer to the problem.
3 2 1 2 3
1
4 2 1 2 3 5
2
5 1 6 2 2 4 5
1
In the first sample, you could set up the following match: $$$(1, 3)$$$.
In the second sample, this is one of the ways you could set up the matches: $$$(2, 5), (1, 3)$$$.
Age of Empires is a fun game that has 3 types of army (archers, melee, cavalry), each of which can have an army value between $$$[l_i, r_i]$$$.
Ahmad is playing a game that he wants to win, and to do so he should select the armies value such that $$$(a_1 \oplus a_2 \oplus a_3)$$$ has a prime number of ones in its binary representation, here $$$a_i$$$ is the value of the army with the $$$i$$$-th type, and $$$\oplus$$$ is the Exclusive OR.
Since Ahmad is busy playing the game, he needs you to calculate the number of ways he could choose the army values such that he can win modulo $$$10^9 + 7$$$.
The first line contains an integer $$$t$$$ $$$(1 \leq t \leq 100)$$$ – the number of test cases.
Then for each test case there are three lines each containing the $$$i$$$-th interval $$$l_i$$$ and $$$r_i$$$ $$$(1 \leq l_i \leq r_i \leq 10^9)$$$ – the possible values for the $$$i$$$-th army type.
For each test case print one integer, the answer to the test case modulo $$$(10^9 + 7)$$$.
11 31 32 3
5
41 102 41 61 43 64 101 31 31 31 11 11 1
101 62 7 0
In the first example, these are the $$$5$$$ ways to choose the armies value:
- $$$(1, 1, 3)$$$;
- $$$(2, 2, 3)$$$;
- $$$(2, 3, 2)$$$;
- $$$(3, 2, 2)$$$;
- $$$(3, 3, 3)$$$.
and all their XOR have the same binary representation $$$011$$$ which has $$$2$$$ ones, and $$$2$$$ is a prime.
Akbar gave Amir a tree with $$$n$$$ vertices and told him that, If we root this tree from a non-leaf vertex, then value of $$$f(v)$$$ for each vertex is equal to :
- If $$$v$$$ is a leaf, $$$f(v) = 1$$$.
- Otherwise if $$$Sub(v)$$$ is defined as the set of vertices of subtree of $$$v$$$ which does not include $$$v$$$, then we have : $$$$$$f(v) = \sum_{A\ \subseteq\ Sub(v)}^{A\ \neq\ \varnothing} (\prod_{u\ \in A}^{} f(u))$$$$$$
$$$\prod_{}^{}$$$ works like $$$\sum_{}^{}$$$ but it calculates product instead of sum.
It is clear that by changing the root, the value of $$$f$$$ may change for different vertices.
Suppose we have rooted the tree from a vertex such that the value of $$$f(root)$$$ is minimum possible, Amir wants to know this value modulo $$$10^9 + 7$$$.
Note that according to the definition of function $$$f$$$, the root should not be a leaf!
In the first line of input, you're given the number of vertices $$$n$$$.
$$$$$$3 \le n \le 10^5$$$$$$
In the next $$$n - 1$$$ lines, you'll receive two integers $$$u$$$ and $$$v$$$ which show that there's an edge between vertices $$$u$$$ and $$$v$$$.
$$$$$$1 \le u, v \le n$$$$$$
It is guaranteed that the given graph is a tree.
Print the answer of the problem modulo $$$10^9 + 7$$$.
7 1 2 2 3 2 4 2 5 3 6 3 7
127
3 1 2 2 3
3
Red numbers in the below pictures show $$$f(v)$$$.
The optimal root for the first sample is vertex $$$2$$$ 
The optimal root for the second sample is vertex $$$2$$$