You are given a positive integer $$$n$$$. Find the number of different integers $$$x$$$ such that $$$n+(x\mod n)=x$$$.
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 $$$n+(x\mod n)=x$$$.
212
1 2
In the first test case, only $$$x=1$$$ satisfies the condition.
In the second test case, $$$x=2$$$ and $$$x=3$$$ satisfy the condition.
There are $$$n$$$ doors. You want to open all of them. There are some rules.
For each $$$2 \le i \le n$$$, you can open the $$$i$$$-th door only if you have already opened the ($$$i-1$$$)-th door.
Initially, you have $$$x$$$ coins.
There is a lock on the $$$i$$$-th door with a cost of $$$c_i$$$. In other words, you need to spend $$$c_i$$$ coins to open the $$$i$$$-th door. If the number of coins you currently have is strictly less than $$$c_i$$$, you will not be able to open the $$$i$$$-th door. After opening the $$$i$$$-th door, you will receive $$$a_i$$$ coins as a prize.
You can do the following operation any number of times:
- Choose an index $$$i$$$, where $$$1 \le i \le n$$$, and set $$$c_i$$$ to $$$0$$$.
Find the minimum number of operations necessary to open all the doors.
The first line contains an integer $$$t$$$ ($$$1 \le t \le 2000$$$), the number of test cases. For each test case:
- The first line contains two integers $$$n$$$ and $$$x$$$ ($$$1 \le n \le 100$$$, $$$1 \le x \le 100$$$).
- The second line contains $$$n$$$ integers $$$c_1,c_2,\ldots,c_n$$$ ($$$1 \le c_i \le 100$$$).
- The third line contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \le a_i \le 100$$$).
For each test case, output the minimum number of operations needed to open all the doors.
31 1113 109 6 51 1 13 105 9 91 2 9
0 1 2
In the first test case, you don't need to perform any operations. You can just spend $$$1$$$ coin to open the first (and only) lock.
In the second test case, you can first set $$$c_1$$$ to $$$0$$$. Then, you can do the following:
- Open the first door. You spend $$$0$$$ coins and receive $$$1$$$ coin. After that, you have $$$11$$$ coins.
- Open the second door. You spend $$$6$$$ coins and receive $$$1$$$ coin. After that, you have $$$6$$$ coins.
- Open the third door. You spend $$$5$$$ coins and receive $$$1$$$ coin. After that, you have $$$2$$$ coins.
Your friend Kaosar asked you to solve a problem.
He will give you an integer $$$n$$$ and a function $$$Q(n,m)$$$, where $$$$$$Q(n,m)=(x+\frac{1}{x^m})^n$$$$$$
He asked you to calculate the sum of all integers $$$m$$$ for which $$$Q(n,m)$$$ has a nonzero constant term.
The first line of the input will contain a single integer $$$t$$$ $$$(1 \le t \le 10^3)$$$ denoting the total number of test cases.
Next $$$t$$$ lines will contain a single integer $$$n$$$ $$$(1 \le n \le 10^9)$$$.
Print the sum of all integers $$$m$$$ for which $$$Q(n,m)$$$ has a nonzero constant term.
3123
0 1 2
In the first test case, only $$$m=0$$$ is valid.
- $$$Q(1,0)=x+1$$$. Here $$$1$$$ is the constant term.
In the second test case, $$$m=0$$$ and $$$m=1$$$ are valid.
- $$$Q(2,0)=x^2 + 2x + 1$$$ . Here $$$1$$$ is the constant term.
- $$$Q(2,1)=x^2+x^{-2}+2$$$. Here $$$2$$$ is the constant term.
An $$$n \times n$$$ matrix $$$a$$$ is called good only if all of the following conditions are satisfied:
- $$$1 \le a_{i,j} \le 3$$$ for all $$$1 \le i \le n$$$, $$$1 \le j \le n$$$.
- The bitwise XOR values of all elements in each row are $$$0$$$.
- The bitwise XOR values of all elements in each column are $$$0$$$.
- The sum of all elements of the matrix reaches the maximum possible value.
You are given an integer $$$n$$$. Your task is to find the number of good matrices of size $$$n \times n$$$.
The first line of input contains an integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of testcases.
Each testcase contains a single integer $$$n$$$ ($$$1 \le n \le 10^6$$$).
For each testcase, print the number of good matrices of size $$$n \times n$$$.
As the answer can be very large, print the answer modulo $$$998244353$$$.
3123
0 1 12
In the first test case, there is no valid good matrix.
In the second test case, $$$\begin{bmatrix} 3 & 3\\ 3 & 3 \end{bmatrix}$$$ is the only good matrix.
You are given an array $$$a$$$ of $$$n$$$ integers. Your task is to find the value of the expression
$$$$$$ \displaystyle\sum_{l = 1}^{n} \displaystyle\sum_{r = l}^{n} f(\displaystyle\prod_{i = l}^{r} a_i) $$$$$$
where $$$f(x)$$$ denotes the number of divisors of $$$x$$$.
For example, $$$f(6)=4$$$ because $$$6$$$ has $$$4$$$ divisors: $$$1,2,3$$$, and $$$6$$$.
Since the answer can be large, output the answer modulo $$$10^9 + 7$$$.
The first line of input contains an integer $$$t$$$ ($$$ 1 \le t \le 10^4 $$$) — the number of testcases. Description of each testcase follows.
The first line of each testcase contains an integer $$$n$$$ ($$$ 1 \le n \le 10^5 $$$) — the length of the array $$$a$$$.
The second line of each testcase contains a sequence of $$$n$$$ integers $$$a_1, a_2, a_3, \cdots, a_n$$$ ($$$ \bf{1 \le a_i \le 20} $$$) — the elements of the array $$$a$$$.
It is guaranteed that the sum of $$$n$$$ over all the testcases does not exceed $$$10^5$$$.
For each testcase, print the answer on a separate line.
3212 861 2 3 4 5 6517 13 20 12 19
22 204 490
In the first test case,
- Taking $$$l = 1$$$ and $$$r = 1$$$, we have $$$\displaystyle\prod_{i = l}^{r} a_i = 12$$$ and $$$f(12) = 6$$$.
- Taking $$$l = 1$$$ and $$$r = 2$$$, we have $$$\displaystyle\prod_{i = l}^{r} a_i = 96$$$ and $$$f(96) = 12$$$.
- Taking $$$l = 2$$$ and $$$r = 2$$$, we have $$$\displaystyle\prod_{i = l}^{r} a_i = 8$$$ and $$$f(8) = 4$$$.
Hence, the answer is equal to $$$6 + 12 + 4 = 22$$$.
You're given two even integers $$$n$$$ and $$$m$$$.
We define the $$$\operatorname{MAD}$$$ (Maximum Appearing Duplicate) of an array as the largest number that appears at least twice in the array. If there is no number that appears at least twice, the $$$\operatorname{MAD}$$$ value is $$$0$$$.
For example, $$$\operatorname{MAD}([1, 2, 1]) = 1$$$, $$$\operatorname{MAD}([2, 2, 3, 3]) = 3$$$, $$$\operatorname{MAD}([1, 2, 3, 4]) = 0$$$.
Construct an array $$$a$$$ of length $$$n$$$ satisfying:
- $$$0 \leq a_i \leq n$$$ for all $$$1 \le i \le n$$$;
- $$$\displaystyle \sum_{1 \le l \lt r \le n} \operatorname{MAD}([a_l,a_{l+1}, \ldots, a_r])=m. $$$
If no such array exists, output $$$-1$$$ instead.
The first line contains one positive integer $$$t\;(1\leq t \leq 10^3)$$$ — the number of test cases.
Each test case consists of one line which contains two integers $$$n$$$ and $$$m$$$ ($$$2 \leq n \le 10^4$$$, $$$0 \le m \le \frac{n \cdot n \cdot (n-1)}{2}$$$). It is guaranteed that $$$n$$$ and $$$m$$$ are both even.
It is guaranteed that the sum of $$$n$$$ over all test cases will not exceed $$$10^4$$$.
For each test case, output an array $$$a$$$ of length $$$n$$$ that satisfies the given conditions. If no such array exists, output $$$-1$$$ instead.
42 04 104 228 40
0 0 4 2 2 4 -1 5 2 1 2 1 5 2 1
In the first test case, $$$$$$\sum_{1 \le l \lt r \le n} \operatorname{MAD}([a_l,a_{l+1}, \ldots, a_r])=\operatorname{MAD}([a_1,a_2])=\operatorname{MAD}([0,0])=0. $$$$$$
In the second test case, the following table summarizes the $$$\operatorname{MAD}$$$ of each subarray. $$$$$$ \begin{array}{c|cccc} & 1 & 2 & 3 & 4 \\ \hline 1 & & 0 & 2 & 4 \\ 2 & & & 2 & 2 \\ 3 & & & & 0 \\ 4 & & & & \end{array} $$$$$$ The sum of all $$$\operatorname{MAD}$$$ values is $$$10$$$, as required.
In the third test case, it is impossible to construct such an array.