You are given a positive integer $$$n$$$. Find the number of different integers $$$x$$$ such that $$$x+(x\mod n)=n$$$.
The first line of the input will contain a single integer $$$t$$$ $$$(1 \le t \le 10^4)$$$ — the total number of test cases.
Each test case contains a single integer $$$n$$$ $$$(1 \le n \le 10^{18}) $$$.
For each test case, output in a new line — the number of different integers $$$x$$$ such that $$$x+(x\mod n)=n$$$.
213
1 1
In the first test case, only $$$x=1$$$ satisfies the condition.
In the second test case, only $$$x=3$$$ satisfies the condition.
You are given a positive integer $$$n$$$.
Note $$$f(n)$$$ as the number of even square divisors of $$$n$$$, and $$$g(n)$$$ as the number of odd square divisors of $$$n$$$.
An even square divisor of a positive integer $$$n$$$ is a divisor of $$$n$$$ that is both a perfect square and an even number. Similarly, an odd square divisor of $$$n$$$ is a divisor of $$$n$$$ that is both a perfect square and an odd number.
Your task is to calculate the value of $$$\frac{f(n)}{g(n)}$$$. It can be proven that the value is always an integer.
The first line of the input will contain a single integer $$$t$$$ $$$(1 \le t \le 2 \cdot 10^5)$$$ — the total number of test cases.
Each test case contains a single integer $$$n$$$ $$$(1 \le n \le 10^{18}) $$$.
For each test case, output in a new line — the value of $$$\frac{f(n)}{g(n)}$$$.
441961000000000000000000
1 0 2 9
In the first test case, $$$f(4)=1$$$ because $$$4$$$ is the only even square divisor of $$$n$$$. And $$$g(4)=1$$$ because $$$1$$$ is the only odd square divisor of $$$n$$$. Thus, $$$\frac{f(n)}{g(n)}=\frac{1}{1}=1$$$.
You are given a permutation $$$ p $$$ of length $$$n$$$.
You can do the following operation any number of times (possibly zero):
- Choose two indices $$$i$$$ and $$$j$$$ $$$(1 \le i \lt j \le n)$$$ such that $$$ (p_i + p_j) $$$ is a composite number. Then swap $$$p_i$$$ and $$$p_j$$$.
A composite number is a positive integer greater than $$$1$$$ that is not a prime number. In other words, a composite number has divisors other than $$$1$$$ and itself. For example, $$$4, 6, 8$$$, and $$$9$$$ are composite numbers.
Determine if you can sort the permutation in increasing order after performing the given operation any number of times (possibly zero).
The first line contains one positive integer $$$t$$$ $$$(1≤t≤2 \cdot 10^5)$$$ — the number of test cases.
Each test case begins with a line containing one integer $$$n$$$ $$$(1≤n≤2 \cdot 10^5)$$$.
The second line of each test case contains n integers $$$p_1…p_n (1≤p_i ≤ n)$$$. It is guaranteed that $$$p$$$ is a permutation.
The sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.
For each test case, output on a separate line:
- YES, if it is possible to sort the given permutation by applying a certain number of operations.
- NO, otherwise.
41122 121 242 1 4 3
Yes No Yes No
You are given a sequence $$$a$$$ of length $$$n$$$. There is a sequence $$$b$$$ which is initially empty. You need to perform $$$n$$$ operations.
In the $$$i$$$-th operation, you can choose one of the following two types of operations:
- insert $$$a_i$$$ into the beginning of $$$b$$$;
- insert $$$a_i$$$ into the end of $$$b$$$.
Solve the following problem for each $$$j$$$, where $$$0 \le j \le n$$$: find the minimum possible number of inversions$$$^\dagger$$$ in $$$b$$$ if exactly $$$j$$$ operations of the first type are performed.
$$$^\dagger$$$ An inversion in a sequence is a pair of elements where the earlier element is greater than the later element. In other words, for a sequence $$$b$$$, a pair $$$(b_i, b_j)$$$ is an inversion only if $$$i \lt j$$$ and $$$b_i \gt b_j$$$.
The first line contains an integer $$$t$$$ ($$$1 \le t \le 10^5$$$), the number of test cases. For each test case:
- The first line contains an integer $$$n$$$ ($$$2 \leq n \leq 3 \cdot 10^5$$$).
- The second line contains $$$n$$$ space-separated integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \leq a_i \leq n$$$).
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$3 \cdot 10^5$$$.
For each test case, output $$$n+1$$$ integers. The $$$j$$$-th integer should be the minimum possible number of inversions when exactly $$$j$$$ operations of the first type are performed, for $$$j=0,\ldots,n$$$.
322 153 2 4 1 263 2 6 1 5 4
1 0 0 6 3 2 1 1 3 7 4 3 3 4 6 8
Consider the first test case.
- If $$$j = 0$$$, the only way is to do two operations of the second type. After that, $$$b=[2,1]$$$ and the number of inversions is $$$1$$$.
- If $$$j = 1$$$, the optimal way is to perform an operation of the second type and then perform an operation of the first type. After that, $$$b=[1,2]$$$ and the number of inversions is $$$0$$$.
- If $$$j = 2$$$, the only way is to do two operations of the first type. After that, $$$b=[1,2]$$$ and the number of inversions is $$$0$$$.
This is the easy version of the problem. The only difference is the maximum number of queries.
This is an interactive problem.
There is a secret permutation $$$p_0, p_1, \ldots, p_{n-1}$$$, which is a permutation of $$$\{0,1,\ldots,n-1\}$$$. There is also a variable $$$mx$$$. At first, $$$mx=4$$$.
Your task is to guess the permutation by using queries of the following type:
- "! $$$i$$$ $$$v$$$" — you answer $$$p_i$$$ $$$(0 \le i \lt n)$$$ is equal to $$$v$$$ $$$(0 \le v \lt n)$$$. If your answer is incorrect, or you have answered twice for the same $$$p_i$$$, the jury will immediately terminate the program and you will receive Wrong Answer. Otherwise, the jury will increase $$$mx$$$ by $$$1$$$.
- "? $$$k$$$ $$$j_1$$$ $$$j_2$$$ $$$\dots$$$ $$$j_k$$$" — select the integer $$$k$$$ ($$$1 \le k \le n$$$) and $$$k$$$ indices $$$j_1$$$, $$$j_2$$$, $$$\dots$$$, $$$j_k$$$ ($$$0 \le j_i \lt n$$$). In response to the query, the jury will return $$$\min(mx,$$$$$$\text{mex}(p_{j_1}, p_{j_2}, \dots, p_{j_k}))$$$.
The $$$\text{mex}(a)$$$ of an array $$$a$$$ is defined as the smallest non-negative integer that does not appear in $$$a$$$. For example, if $$$a = [0, 1, 2, 4]$$$, then $$$\text{mex}(a) = 3$$$ because $$$3$$$ is the smallest non-negative integer not present in $$$a$$$.
Find out the secret permutation using at most $$$9n+1$$$ queries of the second type.
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 200$$$). The description of the test cases follows.
The first line of each test case contains one integer $$$n$$$ ($$$2 \le n \le 1024$$$). It is guaranteed that the sum of $$$n$$$ over all test cases will not exceed $$$1024$$$.
At this moment, the permutation $$$p_0, p_1, \ldots, p_{n-1}$$$ is chosen. The interactor in this task is not adaptive. In other words, the sequence $$$p$$$ is fixed in every test case and does not change during the interaction.
Then you can make queries.
To make a query of the first type, output a line in the format "! $$$i$$$ $$$v$$$" (without quotes). Note that this line is not included in the count of $$$9n+1$$$ queries of the second type.
To make a query of the second type, output a line in the format "? $$$k$$$ $$$j_1$$$ $$$j_2$$$ $$$\dots$$$ $$$j_k$$$" (without quotes) ($$$1 \le k \le n$$$, $$$0 \le j_i \lt n$$$). After each query, read an integer — the answer to your query.
After performing $$$n$$$ queries of the first type (in other words, you have guessed the entire permutation $$$p$$$), if this is the last test case, the jury will terminate the program. Otherwise, the jury will output the next $$$n$$$.
After printing each line, do not forget to output the end of line and flush the output buffer. Otherwise, you will receive the Idleness limit exceeded verdict. To flush, use:
- fflush(stdout) or cout.flush() in C++;
- System.out.flush() in Java;
- stdout.flush() in Python;
- see the documentation for other languages.
2 3 1 0 2 1
? 2 1 0 ! 2 1 ? 1 0 ! 0 2 ! 1 0 ? 1 0 ! 0 0 ! 1 1
In the first test case, the hidden permutation $$$p$$$ is $$$[2,0,1]$$$.
For the query "? 2 1 0", the jury returns $$$1$$$ because $$$\min(mx,\text{mex}(p_1,p_0)) = \min(4,1) =1$$$.
Then, for answer "! 2 1", the jury increases $$$mx$$$ by $$$1$$$ since the answer is correct and you haven't answered for $$$p_2$$$ twice.
For the query "? 1 0", the jury returns $$$0$$$ because $$$\min(mx,\text{mex}(p_0))=\min(5,0) =0$$$.
Note queries are only for understanding statements and do not guarantee finding a unique permutation $$$p$$$.
This is the hard version of the problem. The only difference is the maximum number of queries.
This is an interactive problem.
There is a secret permutation $$$p_0, p_1, \ldots, p_{n-1}$$$, which is a permutation of $$$\{0,1,\ldots,n-1\}$$$. There is also a variable $$$mx$$$. At first, $$$mx=4$$$.
Your task is to guess the permutation by using queries of the following type:
- "! $$$i$$$ $$$v$$$" — you answer $$$p_i$$$ $$$(0 \le i \lt n)$$$ is equal to $$$v$$$ $$$(0 \le v \lt n)$$$. If your answer is incorrect, or you have answered twice for the same $$$p_i$$$, the jury will immediately terminate the program and you will receive Wrong Answer. Otherwise, the jury will increase $$$mx$$$ by $$$1$$$.
- "? $$$k$$$ $$$j_1$$$ $$$j_2$$$ $$$\dots$$$ $$$j_k$$$" — select the integer $$$k$$$ ($$$1 \le k \le n$$$) and $$$k$$$ indices $$$j_1$$$, $$$j_2$$$, $$$\dots$$$, $$$j_k$$$ ($$$0 \le j_i \lt n$$$). In response to the query, the jury will return $$$\min(mx,$$$$$$\text{mex}(p_{j_1}, p_{j_2}, \dots, p_{j_k}))$$$.
The $$$\text{mex}(a)$$$ of an array $$$a$$$ is defined as the smallest non-negative integer that does not appear in $$$a$$$. For example, if $$$a = [0, 1, 2, 4]$$$, then $$$\text{mex}(a) = 3$$$ because $$$3$$$ is the smallest non-negative integer not present in $$$a$$$.
Find out the secret permutation using at most $$$7n$$$ queries of the second type.
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 200$$$). The description of the test cases follows.
The first line of each test case contains one integer $$$n$$$ ($$$2 \le n \le 1024$$$). It is guaranteed that the sum of $$$n$$$ over all test cases will not exceed $$$1024$$$.
At this moment, the permutation $$$p_0, p_1, \ldots, p_{n-1}$$$ is chosen. The interactor in this task is not adaptive. In other words, the sequence $$$p$$$ is fixed in every test case and does not change during the interaction.
Then you can make queries.
To make a query of the first type, output a line in the format "! $$$i$$$ $$$v$$$" (without quotes). Note that this line is not included in the count of $$$7n$$$ queries of the second type.
To make a query of the second type, output a line in the format "? $$$k$$$ $$$j_1$$$ $$$j_2$$$ $$$\dots$$$ $$$j_k$$$" (without quotes) ($$$1 \le k \le n$$$, $$$0 \le j_i \lt n$$$). After each query, read an integer — the answer to your query.
After performing $$$n$$$ queries of the first type (in other words, you have guessed the entire permutation $$$p$$$), if this is the last test case, the jury will terminate the program. Otherwise, the jury will output the next $$$n$$$.
After printing each line, do not forget to output the end of line and flush the output buffer. Otherwise, you will receive the Idleness limit exceeded verdict. To flush, use:
- fflush(stdout) or cout.flush() in C++;
- System.out.flush() in Java;
- stdout.flush() in Python;
- see the documentation for other languages.
2 3 1 0 2 1
? 2 1 0 ! 2 1 ? 1 0 ! 0 2 ! 1 0 ? 1 0 ! 0 0 ! 1 1
In the first test case, the hidden permutation $$$p$$$ is $$$[2,0,1]$$$.
For the query "? 2 1 0", the jury returns $$$1$$$ because $$$\min(mx,\text{mex}(p_1,p_0)) = \min(4,1) =1$$$.
Then, for answer "! 2 1", the jury increases $$$mx$$$ by $$$1$$$ since the answer is correct and you haven't answered for $$$p_2$$$ twice.
For the query "? 1 0", the jury returns $$$0$$$ because $$$\min(mx,\text{mex}(p_0))=\min(5,0) =0$$$.
Note queries are only for understanding statements and do not guarantee finding a unique permutation $$$p$$$.
Alice and Bob are playing a game on an array $$$a$$$ of length $$$n$$$. They take turns performing the operation. Alice takes the lead. The person who cannot make a move loses.
In an operation, a player can:
- choose a range $$$[l,r]$$$ ($$$1 \leq l \leq r \leq 10^9$$$);
- if $$$l \lt r$$$, choose all indices $$$i$$$ such that $$$a_i \in [l,r-1]$$$ and decrease $$$a_i$$$ by $$$1$$$;
- then, choose some (possibly zero) indices $$$i$$$ such that $$$a_i=r$$$ and decrease $$$a_i$$$ by $$$1$$$.
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^5$$$). The description of the test cases follows.
The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 3\cdot 10^5$$$).
The second line of each test case contains $$$n$$$ integers $$$a_1,a_2,\ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$).
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$3 \cdot 10^5$$$.
For each test case, if Alice has a winning strategy, output YES. Otherwise, output NO.
671 3 1 3 3 4 541 1 1 11100000000031 2 341 2 3 486 10 9 2 8 6 5 4
YES YES NO NO YES NO
In the first test case, Alice can choose the range $$$[1,3]$$$, then choose all indices satisfying $$$a_i \in [1,2]$$$ and decrease $$$a_i$$$ by $$$1$$$. In other words, $$$a_1$$$ and $$$a_3$$$ are decreased by $$$1$$$. After that, $$$a=[0,3,0,3,3,4,5]$$$. Then, Alice can choose some $$$i$$$ satisfying $$$a_i=3$$$. In this case, Alice chooses $$$i=2,4$$$. After that,$$$a=[0,2,0,2,3,4,5]$$$;
It can be proven Alice has a winning strategy after the operation above.
In the second test case, Alice can choose $$$[1,1]$$$. Then, Alice can choose some indices $$$i$$$ satisfying $$$a_i=1$$$. Here, Alice chooses $$$i=1,2,3,4$$$. After this operation, $$$a=[0,0,0,0]$$$ and Alice wins.