Skip to content
TheChatArchiveThe Chat Archive
o1-preview-2024-09-12· OpenAIAi2 WildChat-4.8M (AI2)

Artem wrote the digit d on the board exactly n! times in a row. So, he got the number…

  1. 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 .

  2. 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:

    1. The number is always divisible by 1: Since any number is divisible by 1, we always start by including 1 in our list.

    2. 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} ).
    3. Divisibility by 5:

      • ( N ) will end with the digit ( d ), so it is divisible by 5 if ( d = 5 ).
    4. 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.
    5. 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))))