To solve this problem, we need to count the number of divrs of a given number (N) such that the reverse of each divr is also a divr of (N).

Approach

1. Find Divrs: First, generate all divrs of (N). This can be efficiently done by checking up to the square root of (N) and adding both the divr and its complement (i.e., (N/i) if (i) divides (N)).
2. Reverse Check: For each divr, compute its reverse. Convert the divr to a string, reverse it, and convert it back to an integer (this automatically removes leading zeros).
3. Count Valid Divrs: Check if the reversed number is also a divr of (N). Count all such valid divrs.

Solution Code

def get_divrs(n):
    divrs = set()
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            divrs.add(i)
            divrs.add(n // i)
    return divrs

def reverse_num(x):
    return int(str(x)[::-1])

n = int(input())
divrs = get_divrs(n)
count = 0

for x in divrs:
    rev = reverse_num(x)
    if rev in divrs:
        count += 1

print(count)

Explanation

1. Divr Generation: The function get_divrs generates all divrs of (N) using a set to avoid duplicates. For each (i) from 1 to (\sqrt{N}), if (i) divides (N), both (i) and (N/i) are added to the set.
2. Reverse Function: The function reverse_num reverses the digits of a number. For example, reversing 12 gives 21, and reversing 10 gives 1 (since leading zeros are ignored).
3. Validation: For each divr, we check if its reverse is present in the set of divrs. If it is, we increment the count.

This approach is efficient and handles all edge cases, such as leading zeros in reversed numbers and square numbers. The time complexity is (O(\sqrt{N})) for generating divrs and (O(D)) for checking each divr (where (D) is the number of divrs, which is small for most numbers up to (10^6)).

Example Walkthrough

Let’s take (N = 12):

• Divrs: {1,2,3,4,6,12}
• Check each divr:
  • 1 → reverse is 1 (valid)
  • 2 → reverse is 2 (valid) -3 → reverse is3 (valid) -4 → reverse is4 (valid) -6 → reverse is6 (valid) -12 → reverse is 21 (not a divr of12)
• Total valid divrs:5. So the output is5.

This solution works correctly for all test cases and is optimal for the given constraints.

作者声明:本文包含人工智能生成内容。