Artem wrote the digit d on the board exactly n! times in a row. So, he got the number…
- User
Artem wrote the digit d on the board exactly n! times in a row. So, he got the number dddddd…ddd (exactly n! digits).
Now he is curious about which odd digits from 1 to 9 divide the number written on the board.
Input The first line contains a single integer t (1≤t≤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≤n≤109 , 1≤d≤9 ).
Output For each test case, output the odd digits in ascending order that divide the number written on the board.
Example InputCopy 3 2 6 7 1 8 5 OutputCopy 1 3 1 3 7 9 1 3 5 7 9 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⋅2⋅3⋅4⋅5=120 .
- Assistant
To solve this problem, we need to determine which odd digits from 1 to 9 divide the number ( N ), where ( N ) is a number composed of ( n! ) repetitions of the digit ( d ). Here's how we can do it:
-
The number is always divisible by 1: Since any number is divisible by 1, we always start by including 1 in our list.
-
Divisibility by 3:
- For ( n \geq 3 ), ( n! ) is divisible by 3, so the sum of digits ( (n! \times d) ) is also divisible by 3. Hence, ( N ) is divisible by 3.
- For ( n = 2 ), ( n! = 2 ):
- ( N ) is divisible by 3 if ( 2d \mod 3 = 0 ), which happens when ( d \in {3, 6, 9} ).
-
Divisibility by 5:
- ( N ) will end with the digit ( d ), so it is divisible by 5 if ( d = 5 ).
-
Divisibility by 7:
- For ( n \geq 3 ), ( N ) is divisible by 7 because ( n! \mod 6 = 0 ) (since 7 is prime and the exponent reduces modulo 6 due to Fermat's Little Theorem), leading to ( N \mod 7 = 0 ).
- For ( n = 2 ), ( N ) is not divisible by 7.
-
Divisibility by 9:
- For ( n \geq 6 ), ( n! ) is divisible by 9, so ( N ) is divisible by 9.
- For ( n < 6 ), we calculate ( n! \mod 9 ) and check if ( (n! \mod 9) \times d \mod 9 = 0 ):
- For ( n = 2 ), ( N ) is divisible by 9 if ( 2d \mod 9 = 0 ), which happens when ( d = 9 ).
- For ( n = 3 ) or ( n = 4 ), ( N ) is divisible by 9 if ( 6d \mod 9 = 0 ), which happens when ( d \in {3, 6, 9} ).
- For ( n = 5 ), ( N ) is divisible by 9 if ( 3d \mod 9 = 0 ), which happens when ( d \in {3, 6, 9} ).
Applying these rules for each test case will give us the required set of odd digits that divide ( N ).
Here's the implementation of the above logic:
t = int(input()) for _ in range(t): n, d = map(int, input().split()) ans = [1] # Start with 1 as every number is divisible by 1 n_factorial_mod3 = 0 n_factorial_mod9 = 0 n_factorial_mod5 = 0 n_factorial_mod7 = 0 # Divisibility by 3 if n >= 3: ans.append(3) else: if (2 * d) % 3 == 0: ans.append(3) # Divisibility by 5 if d == 5: ans.append(5) # Divisibility by 7 if n >= 3: ans.append(7) else: pass # For n=2, N is not divisible by 7 # Divisibility by 9 if n >= 6: ans.append(9) else: n_factorial_mod9 = 1 for i in range(2, n+1): n_factorial_mod9 = (n_factorial_mod9 * i) % 9 if (n_factorial_mod9 * d) % 9 == 0: ans.append(9) print(' '.join(map(str, sorted(ans)))) -