Busy Beaver is given a positive integer $$$k$$$ ($$$1 \le k \le 10^{18}$$$) written in base $$$10$$$. Then, he repeatedly performs the following operation:
Choose a digit in $$$k$$$ that is greater than $$$1$$$. If $$$k$$$ is divisible by that digit, divide $$$k$$$ by that digit. Repeat this process on the resulting number until either $$$1$$$ is reached or there are no more legal operations. Call $$$k$$$ valid if there exists a way to reduce it to $$$1$$$ via this operation.
Compute the number of $$$k$$$ in the range $$$1, \dots, N$$$ that are valid.
The first line of input contains the given integer $$$N$$$ ($$$1 \le N \le 10^{18}$$$).
Output a single line, with a single integer equivalent to the number of integers from $$$1$$$ to $$$N$$$ that have a way to reach $$$1$$$ using the operation.
There are two subtasks for this problem.
- ($$$25$$$ Points): $$$N \le 10^5$$$.
- ($$$75$$$ Points): No additional constraints.
9
9
13
10
In the first test case, all integers from $$$1$$$ to $$$9$$$ can be divided by themselves to reach $$$1$$$, so the answer is $$$9$$$.
In the second test case, all integers from $$$1$$$ to $$$9$$$ are valid, as mentioned in the first test case. $$$10$$$, $$$11$$$, and $$$13$$$ have no digits greater than $$$1$$$ that are divisors of themselves, and therefore cannot be reduced to $$$1$$$. However, $$$12$$$ can be divided by $$$2$$$ to get $$$6$$$, which can in turn be divided by $$$6$$$ to get $$$1$$$. Therefore, the numbers $$$1$$$ through $$$9$$$ and $$$12$$$ are valid, giving an answer of $$$10$$$.
Busy Beaver is playing his favorite adventure game, where he battles wild monsters with monsters of his own!
In this game, there are two types of monsters: light and dark. Each monster has exactly one type, and some positive integer power level. A monster with power $$$p$$$ can defeat another monster $$$q$$$ if either $$$p \geq q$$$, or if they have the same type and $$$2p \geq q$$$.
Busy Beaver has just encountered $$$N$$$ monsters, and he also has $$$N$$$ monsters in his party. To defend against the encounter, he needs to pair his monsters with the opposing monsters such that in each pair, Busy Beaver's monster can defeat the opposing monster according to the rules above. Given the types and power levels of each of the monsters, please report whether or not such a pairing exists.
Each test contains multiple test cases. The first line of input contains a single integer $$$T$$$ $$$(1 \leq T \leq 10^5)$$$, the number of test cases. The description of each test case follows.
The first line of each test case contains a single positive integer $$$N$$$ ($$$1 \leq N \leq 2 \cdot 10^5$$$).
Then, $$$N$$$ lines of input follow, describing Busy Beaver's monsters. The $$$i$$$th line contains two positive integers $$$p_i, s_i$$$ ($$$1 \leq p_i \leq 10^9, s_i \in \{0, 1\}$$$) — the power level $$$p_i$$$ and type $$$s_i$$$ of the $$$i$$$th monster. $$$s_i = 0$$$ denotes a light-type monster, and $$$s_i = 1$$$ denotes a dark-type monster.
After that, there are $$$N$$$ more lines of input, describing the encountered monsters. The $$$i$$$th line contains two positive integers $$$q_i, t_i$$$ ($$$1 \leq q_i \leq 10^9, t_i \in \{0, 1\}$$$) — the power level $$$q_i$$$ and type $$$t_i$$$ of the $$$i$$$th monster. $$$t_i = 0$$$ denotes a light-type monster, and $$$t_i = 1$$$ denotes a dark-type monster.
It is guaranteed that the sum of $$$N$$$ across all test cases is no more than $$$2 \cdot 10^5$$$.
For each test case, output "YES" (without quotes) if a desired pairing exists, and "NO" (without quotes) otherwise.
You can output "YES" and "NO" in any case (for example, strings "yES", "yes" and "Yes" will be recognized as a positive response).
There are two subtasks for this problem.
- ($$$30$$$ points): The sum of $$$N$$$ across all test cases does not exceed $$$2 \cdot 10^3$$$.
- ($$$70$$$ points): No additional constraints.
242 03 01 11 11 02 03 02 121 15 11 01000000000 0
YES NO
In the sample input, there are two test cases. For the first case, we can construct a pairing as follows:
- Your light type monster of power level $$$2$$$ can defeat the identical opposing monster.
- Your light type monster of power level $$$3$$$ can defeat the identical opposing monster.
- Your first dark type monster of power level $$$1$$$ can defeat the opposing dark type monster of power level $$$2$$$.
- Your second dark type monster of power level $$$1$$$ can defeat the opposing light type monster of power level $$$1$$$.
In the second case, it can be shown that no pairing exists.
Let $$$N, K$$$ be positive integers satisfying $$$K \leq N$$$. Busy Beaver has a permutation$$$^{\text{∗}}$$$ $$$a_1, \ldots, a_N$$$ of $$$1, \dots, N$$$. A length $$$K$$$ subsequence$$$^{\text{†}}$$$ of $$$a_1, \ldots, a_N$$$ given by $$$b_1, \ldots, b_K$$$ is interesting if the longest increasing$$$^{\text{‡}}$$$ subsequence of $$$b_1, \dots, b_K$$$ has length at most $$$\frac{K+1}{2}$$$.
Determine whether Busy Beaver's permutation has an interesting subsequence of length $$$K$$$, and if it exists, provide such an example of an interesting subsequence.
$$$^{\text{∗}}$$$A permutation of length $$$N$$$ is an array consisting of $$$N$$$ distinct integers from $$$1$$$ to $$$N$$$ in arbitrary order. For example, $$$[2,3,1,5,4]$$$ is a permutation, but $$$[1,2,2]$$$ is not a permutation ($$$2$$$ appears twice in the array), and $$$[1,3,4]$$$ is also not a permutation ($$$N=3$$$ but there is $$$4$$$ in the array).
$$$^{\text{†}}$$$A sequence $$$a$$$ is a subsequence of a sequence $$$b$$$ if $$$a$$$ can be obtained from $$$b$$$ by the deletion of several (possibly, zero or all) elements.
$$$^{\text{‡}}$$$A sequence $$$a_1, \dots, a_m$$$ is increasing if $$$a_1 \lt a_2 \lt \dots \lt a_{m-1} \lt a_m$$$. For instance, $$$[1, 2, 5]$$$ is increasing while $$$[2, 5, 1]$$$ is not.
Each test contains multiple test cases. The first line of input contains a single integer $$$T$$$ $$$(1 \leq T \leq 10^5)$$$, the number of test cases. The description of each test case follows.
The first line of each test case contains two space-separated integers $$$N, K$$$ ($$$1 \leq K \leq N \leq 2 \cdot 10^5$$$).
The second line of each test case contains $$$N$$$ integers $$$a_1, a_2, \ldots, a_N$$$ ($$$1 \leq a_i \leq N$$$, $$$a_i$$$ pairwise distinct) — Busy Beaver's permutation.
It is guaranteed that the sum of $$$N$$$ across all test cases is no more than $$$2 \cdot 10^5$$$.
For each test case, output "YES" (without quotes) if there exists an interesting subsequence, and "NO" (without quotes) otherwise. You can output "YES" and "NO" in any case (for example, strings "yES", "yes" and "Yes" will be recognized as a positive response).
Then, if you responded with "YES", print a second line consisting of $$$K$$$ space-separated integers $$$i_1, \dots, i_K$$$ ($$$1 \leq i_1 \lt \dots \lt i_K \leq n$$$), the indices of the permutation such that $$$a_{i_1}, \dots, a_{i_K}$$$ is an interesting subsequence. If there are multiple possible solutions, print any of them.
You will receive $$$50\%$$$ of the points for each subtask if the YES/NO responses are correct, but the provided values of $$$i_1, \dots, i_K$$$ are not. For each test case, you must still output the indices $$$i_1 \lt \dots \lt i_K$$$ of a length-$$$K$$$ subsequence to receive partial credit for YES/NO responses. For instance, you could output $$$(i_1, \dots, i_K) = (1, \dots, K)$$$ but not $$$(i_1, \dots, i_K) = (1, \dots, 1)$$$.
There are three subtasks for this problem.
- ($$$10$$$ points): $$$K \leq 4$$$.
- ($$$20$$$ points): The permutation has at most one index $$$i$$$ ($$$1 \leq i \lt N$$$) such that $$$a_i \gt a_{i+1}$$$.
- ($$$70$$$ points): No additional constraints.
104 24 2 1 37 33 1 4 5 7 2 68 84 5 6 7 8 1 2 36 45 2 4 3 1 69 81 3 2 4 6 5 7 9 89 71 3 2 4 6 5 7 9 89 51 6 8 9 2 5 3 4 73 23 2 13 21 2 31 11
YES 2 3 YES 5 6 7 NO YES 1 2 4 5 NO YES 2 3 5 6 7 8 9 YES 3 4 6 7 8 YES 2 3 NO YES 1
In the first test case, the subsequence $$$[a_2, a_3] = [2, 1]$$$ has two longest increasing subsequences $$$[2]$$$ and $$$[1]$$$, each of which has length at most $$$\frac{2 + 1}{2} = \frac 32.$$$ It is therefore an interesting subsequence.
In the second test case, the subsequence $$$[a_5, a_6, a_7] = [7, 2, 6]$$$ has a unique longest increasing subsequence given by $$$[2, 6]$$$, which has length at most $$$\frac{3 + 1}{2} = 2.$$$ It is therefore an interesting subsequence.
In the third test case, the only subsequence of length $$$8$$$ is the entire sequence $$$[a_1, \dots, a_8] = [4, 5, 6, 7, 8, 1, 2, 3]$$$. The longest increasing subsequence of this sequence is $$$[4, 5, 6, 7, 8]$$$. As its length is greater than $$$\frac{8 + 1}{2} = \frac 92$$$, there is no interesting subsequence.
Busy Beaver likes to draw lines on paper. However, he gets sad when two lines intersect. One night, he dreamed of a masterpiece drawing consisting of many rays with no intersections. But, when he woke up, he only remembered where the rays started, and not which direction they went in! Help him recreate the drawing.
Formally, you are given $$$N$$$ points on the plane, each with distinct integer $$$x$$$ and $$$y$$$ coordinates in the range $$$[1, N]$$$. Each point is labeled with either UD or LR. For each UD point, you must draw an infinitely long ray starting at that point that goes vertically either up or down. Likewise, for each LR point, you must draw an infinitely long ray starting at that point that goes horizontally either left or right.
Out of all $$$2^N$$$ ways to assign directions to each point, figure out whether there is an assignment where no two rays intersect, and if one exists, output the number of satisfying assignments, modulo $$$10^9 + 7$$$.
For your convenience, we promise that if $$$x$$$ is the number of satisfying assignments and $$$x \gt 0$$$, then $$$x \not \equiv 0 \pmod{10^9+7}$$$.
Each test contains multiple test cases. The first line of input contains a single integer $$$T$$$ $$$(1 \leq T \leq 10^4)$$$, the number of test cases.
The first line of each test case contains a positive integer $$$N$$$ ($$$1 \le N \le 10^3)$$$, representing the number of points.
The $$$i$$$-th of the next $$$N$$$ lines contain two integers $$$x_i, y_i$$$ and a string $$$s_i$$$, where $$$(x_i, y_i)$$$ denotes the location of the $$$i$$$-th point, and $$$s_i \in \{\tt{UD}, \tt{LR}\}$$$ denotes the allowed ray directions from the point.
$$$x_i$$$ are guaranteed to be pairwise distinct integers in the range $$$[1, N]$$$, and the same holds for $$$y_i$$$.
You are guaranteed that the sum of $$$N$$$ over all test cases is at most $$$10^4$$$.
For each of the $$$T$$$ test cases, output two lines.
On the first line, output "YES" or "NO", representing whether a satisfying assignment exists. You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.
On the second line, output the number of satisfying assignments, modulo $$$10^9+7$$$.
You will receive $$$50\%$$$ of the points for each subtask if the YES/NO responses are correct, but the count of satisfying assignments are incorrect.
- ($$$10$$$ points): $$$N \le 10$$$.
- ($$$40$$$ points): $$$N \le 100$$$.
- ($$$50$$$ points): No additional constraints.
321 1 UD2 2 UD21 2 UD2 1 LR71 5 UD2 3 UD3 4 LR4 1 LR5 7 LR6 2 UD7 6 UD
YES 4 YES 3 NO 0
In the first test case, any of the $$$2^2 = 4$$$ assignments results in no intersections.
In the second test case, if the first point is assigned D and the second point is assigned L, there is an intersection of the two rays at $$$(1, 1)$$$. All $$$3$$$ other assignments work.
In the third test case, all assignments result in at least one intersection.
The second test case is depicted below.
For his number theory homework, Busy Beaver is given $$$T$$$ pairs of a large prime $$$p$$$ and an integer $$$x$$$. For each pair, Busy Beaver needs to find a subset of $$$\{1,\frac 12,\frac 13,\cdots,\frac 1{5000}\}$$$ of size at most $$$S$$$ whose sum is equal to $$$x$$$ modulo $$$p$$$. Can you help him find such subsets?
A rational number $$$\frac ab$$$ is equal to $$$x$$$ modulo $$$p$$$ if $$$a \equiv bx \pmod p$$$.
The first line contains two integers $$$T$$$ and $$$S$$$ ($$$1 \le T \le 1000$$$, $$$150 \le S \le 5000$$$), indicating the number of testcases and the maximum size of the subset.
Each of the next $$$T$$$ lines contains two integers $$$p$$$ and $$$x$$$ ($$$10^8 \le p \le 10^{18}$$$, $$$0 \le x \le p-1$$$), where $$$p$$$ is prime.
For each testcase, output one line indicating the answer. Start with some integer $$$k$$$ ($$$0 \le k \le S$$$), indicating the size of the subset, and then follow with $$$k$$$ distinct integers $$$a_1,\dots,a_k$$$ in increasing order ($$$1 \le a_1 \lt a_2 \lt \dots \lt a_k \le 5000$$$).
Your output should satisfy $$$\frac{1}{a_1} + \frac{1}{a_2} + \dots + \frac{1}{a_k} \equiv x \pmod p$$$.
It can be proven that for all $$$p$$$, $$$x$$$ satisfying the input constraints, such a subset always exists.
- ($$$10$$$ points) $$$T \le 10$$$, $$$p \le 10^9$$$.
- ($$$20$$$ points) $$$T \le 10$$$, $$$p \le 10^{15}$$$, $$$S = 5000$$$.
- ($$$30$$$ points) $$$S = 5000$$$.
- ($$$40$$$ points) No additional constraints.
4 150998244353 01000000007 11000000007 5000000041000000007 642833014
0 1 1 1 2 3 1 19 2025
In the first test case, the empty subset sums to $$$x = 0$$$ modulo $$$p = 998244353$$$.
In the second test case, $$$\frac{1}{1} \equiv 1 \pmod {1000000007}$$$.
In the third test case, $$$\frac{1}{2} \equiv 500000004 \pmod {1000000007}$$$.
In the fourth test case, $$$\frac{1}{1} + \frac{1}{19} + \frac{1}{2025} \equiv 642833014 \pmod {1000000007}$$$.