結果

問題 No.443 GCD of Permutation
ユーザー qwewe
提出日時 2025-05-14 13:18:19
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 3,341 bytes
コンパイル時間 181 ms
コンパイル使用メモリ 82,236 KB
実行使用メモリ 67,744 KB
最終ジャッジ日時 2025-05-14 13:19:15
合計ジャッジ時間 2,987 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 18 RE * 10
権限があれば一括ダウンロードができます

ソースコード

diff # 

import math
import sys

# Function to compute the greatest common divisor (GCD) of a list of non-negative integers.
# Uses the property gcd(a, b, c) = gcd(a, gcd(b, c)).
# It handles lists containing zeros correctly: gcd(x, 0) = x.
# If the list contains only zeros or is empty, the GCD is 0.
def list_gcd(numbers):
    """
    Computes the greatest common divisor of a list of non-negative integers.
    Returns 0 if the list is empty or contains only zeros.
    """
    # Filter out zeros initially. If only zeros remain, the GCD is 0.
    non_zero_numbers = [x for x in numbers if x != 0]
    
    if not non_zero_numbers:
         # This happens if the input list `numbers` contains only 0s or is empty.
         return 0

    # Compute GCD iteratively for the non-zero numbers.
    # Initialize result with the first non-zero number.
    result = non_zero_numbers[0]
    # Iterate through the rest of the non-zero numbers.
    for i in range(1, len(non_zero_numbers)):
        result = math.gcd(result, non_zero_numbers[i])
    
    # math.gcd always returns a non-negative result for non-negative inputs.
    return result

def solve():
    # Read the input integer N as a string. N can be very large.
    N_str = sys.stdin.readline().strip()
    
    # Convert the input string N_str to a large integer M0.
    # M0 is one of the numbers formed by permuting the digits of N (specifically, N itself).
    # Since N is positive, M0 will be positive.
    M0 = int(N_str) 
    
    # Count the occurrences of each digit ('0' through '9') in N.
    counts = [0] * 10
    for digit_char in N_str:
        counts[int(digit_char)] += 1
    
    # Identify the set of distinct digits present in N.
    distinct_digits = []
    for i in range(10):
        if counts[i] > 0:
            distinct_digits.append(i)
    
    # Find the minimum digit present among the distinct digits.
    # Since distinct_digits is populated in increasing order (0 to 9),
    # the first element is the minimum.
    d_min = distinct_digits[0] 
        
    # Calculate the differences (d - d_min) for all distinct digits d.
    # This list will contain non-negative integers, including 0 (from d_min - d_min).
    diffs = []
    for d in distinct_digits:
         diffs.append(d - d_min) 

    # Compute K = GCD of these differences.
    # K represents the greatest common divisor of the differences between any pair of digits present in N.
    # K = GCD(d - d_min for d in distinct_digits) = GCD(d1-d_min, d2-d_min, ...)
    # This is equivalent to GCD(|di - dj|) for all pairs of distinct digits di, dj.
    K = list_gcd(diffs)
    
    # If K is 0, it implies all differences were 0. This happens if and only if
    # there is only one distinct digit type present in N. In this case, 9*K = 0.
    NineK = 9 * K
    
    # The final GCD of all numbers in set S is GCD(M0, 9K).
    # We use the property that any number M in S must be congruent to M0 modulo 9K.
    # Therefore, the GCD of all numbers in S must divide both M0 and 9K.
    # Also, GCD(M0, 9K) divides all numbers in S.
    # Thus, GCD(S) = GCD(M0, 9K).
    # Note that math.gcd(X, 0) correctly returns abs(X). Since M0 is positive, it returns M0.
    final_gcd = math.gcd(M0, NineK)
    
    # Print the final GCD result.
    print(final_gcd)

# Call the solve function to run the program.
solve()
0