Digits
Contest: Educational Codeforces Round 173 (Rated for Div. 2)
Difficulty rating: 1100
Tags: math, number theory

Artem wrote the digit $$$d$$$ on the board exactly $$$n!$$$ times in a row. So, he got the number $$$dddddd \dots ddd$$$ (exactly $$$n!$$$ digits).

Now he is curious about which odd digits from $$$1$$$ to $$$9$$$ divide the number written on the board.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases. The next $$$t$$$ test cases follow.

Each test case consists of a single line containing two integers $$$n$$$ and $$$d$$$ ($$$2 \le n \le 10^9$$$, $$$1 \le d \le 9$$$).

Output format:
For each test case, output the odd digits in ascending order that divide the number written on the board.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
The factorial of a positive integer $$$n$$$ ($$$n!$$$) is the product of all integers from $$$1$$$ to $$$n$$$. For example, the factorial of $$$5$$$ is $$$1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 = 120$$$.

Example input:
3
2 6
7 1
8 5

Example output:
1 3 
1 3 7 9 
1 3 5 7 9

Editorial:
There are several ways to solve this problem. I will describe two of them.
Using divisibility rules (a lot of math involved):
We can try divisibility rules for all odd integers from $$$1$$$ to $$$9$$$ and find out whether they work for our numbers:
• $$$1$$$ is always the answer, since every integer is divisible by $$$1$$$:
• a number is divisible by $$$3$$$ iff its sum of digits is divisible by $$$3$$$. Since our number consists of $$$n!$$$ digits $$$d$$$, then either $$$n!$$$ or $$$d$$$ should be divisible by $$$3$$$; so, $$$n \ge 3$$$ or $$$d \bmod 3 = 0$$$;
• a number is divisible by $$$9$$$ iff its sum of digits is divisible by $$$9$$$. This is a bit trickier than the case with $$$3$$$, because it is possible that both $$$n!$$$ and $$$d$$$ are divisible by $$$3$$$ (not $$$9$$$), and it makes the sum of digits divisible by $$$9$$$;
• a number is divisible by $$$5$$$ iff its last digit is $$$5$$$ or $$$0$$$. Just check that $$$d=5$$$, and that's it;
• probably the trickiest case: a number is divisible by $$$7$$$ iff, when this number is split into blocks of $$$3$$$ digits (possibly with the first block shorter than $$$3$$$ digits), the sign-alternating sum of these blocks is divisible by $$$7$$$. Like, $$$1234569$$$ is divisible by $$$7$$$ because $$$(1-234+569)$$$ is divisible by $$$7$$$. If we apply this rule to our numbers from the problem, we can use the fact that when $$$n \ge 3$$$, the number can be split into several blocks of length $$$6$$$, and each such block changes the alternating sum by $$$0$$$. So, if $$$n \ge 3$$$ or $$$d = 7$$$, our number is divisible by $$$7$$$.
Almost brute force (much less math involved):
First, we actually need a little bit of math. If you take a number consisting of $$$n!$$$ digits equal to $$$d$$$, it is always divisible by $$$(n-1)!$$$ digits equal to $$$d$$$. This is because, if you write some integer repeatedly, the resulting number will be divisible by the original number, like, for example, $$$424242$$$ is divisible by $$$42$$$.
So, if for some $$$n = k$$$, the number is divisible by some digit, then for $$$n = k+1$$$, the number will also be divisible for some digit.
This means that there exists an integer $$$m$$$ such that for all integers $$$n \ge m$$$, the results are the same if you use the same digit $$$d$$$. So, we can set $$$n = \min(n, m)$$$, and if $$$m$$$ is small enough, use brute force.
What is the value of $$$m$$$? The samples tell us that the number consisting of $$$7!$$$ ones is divisible by $$$1$$$, $$$3$$$, $$$7$$$ and $$$9$$$ (and divisibility by $$$5$$$ depends only on $$$d$$$), so you can actually use $$$m=7$$$. It is also possible to reduce $$$m$$$ to $$$6$$$, but this is not required.
So, the solution is: reduce $$$n$$$ to something like $$$7$$$ if it is greater than $$$7$$$, then use brute force. You can either calculate the remainder of a big number modulo small number using a for-loop, or, if you code in Java or Python, use built-in big integers (just be careful with Python, modern versions of it forbid some operations with integers longer than $$$4300$$$ digits, you might need to override that behavior).