結果

問題 No.3054 Modulo Inequalities
ユーザー qwewe
提出日時 2025-05-14 12:56:18
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,280 bytes
コンパイル時間 257 ms
コンパイル使用メモリ 82,352 KB
実行使用メモリ 77,260 KB
最終ジャッジ日時 2025-05-14 12:58:42
合計ジャッジ時間 10,033 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other WA * 16 RE * 15
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def solve():
    # Read the target number of digits X from standard input
    X = int(sys.stdin.readline())

    # The problem asks for positive integers (a, b, c) such that:
    # 1. a^2 + b^2 = c^2  (Pythagorean triple)
    # 2. b = a + 1        (Consecutive integers for legs)
    # 3. c has exactly X digits in base 10.
    
    # Substituting b = a + 1 into the Pythagorean equation:
    # a^2 + (a+1)^2 = c^2
    # a^2 + a^2 + 2a + 1 = c^2
    # 2a^2 + 2a + 1 = c^2

    # Multiply by 2: 4a^2 + 4a + 2 = 2c^2
    # (2a + 1)^2 + 1 = 2c^2
    # Let y = 2a + 1. Then the equation becomes y^2 + 1 = 2c^2, or y^2 - 2c^2 = -1.
    # This is a Pell-type equation.
    
    # The fundamental solution to the associated Pell equation p^2 - 2q^2 = 1 is (p1, q1) = (3, 2).
    # The solutions (y_k, c_k) to y^2 - 2c^2 = -1 are generated by the recurrence relations derived from the fundamental solutions.
    # The first positive integer solution (a > 0) corresponds to k=2 in the sequence generated by (1 + sqrt(2)) * (3 + 2*sqrt(2))^(k-1).
    # For k=2, (y, c) = (7, 5). This gives a = (7-1)/2 = 3, b = 4, c = 5. (3, 4, 5) is the smallest solution.
    # The recurrence relations for subsequent solutions (y_k, c_k) are:
    # y_{k+1} = 3 * y_k + 4 * c_k
    # c_{k+1} = 2 * y_k + 3 * c_k
    
    # Initialize with the first positive solution (k=2 state)
    y = 7
    c = 5
    
    # Loop to find the solution where c has exactly X digits
    # It starts by checking the initial state (k=2), then iteratively computes subsequent states (k=3, 4, ...)
    while True:
        # Calculate the number of digits of the current c value.
        # In Python, len(str(number)) is a simple way to get the number of digits for large integers.
        num_digits = len(str(c))
        
        # Check if the number of digits matches the target X
        if num_digits == X:
            # If matched, we have found the required triplet.
            # Calculate a and b from the current y value.
            # Since y = 2a + 1, we have a = (y - 1) // 2.
            # The problem specifies b = a + 1.
            a = (y - 1) // 2
            b = a + 1
            
            # Print the resulting triplet (a, b, c) separated by spaces.
            print(f"{a} {b} {c}")
            return # Exit the function as the solution is found
        
        # If the number of digits does not match X:
        # The problem statement guarantees that a solution exists.
        # The properties of Pell equation solutions ensure that the number of digits of c_k is non-decreasing
        # and eventually reaches any target number of digits X within the specified range.
        # Therefore, if num_digits is not X, it must be less than X, and we need to compute the next solution state.
        
        # Store the current values of y and c to use in the recurrence calculation for the next state.
        # This avoids using updated values within the same step.
        current_y = y
        current_c = c
        
        # Apply the recurrence relations to compute the next pair (y, c)
        y = 3 * current_y + 4 * current_c
        c = 2 * current_y + 3 * current_c
        # The loop continues with the new (y, c) pair.

# Call the solve function to start the process
solve()
0