結果

問題 No.2271 平方根の１３桁精度近似計算
コンテスト
ユーザー lam6er
提出日時 2025-03-20 20:50:46
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,481 bytes
コンパイル時間 310 ms
コンパイル使用メモリ 82,836 KB
実行使用メモリ 54,372 KB
最終ジャッジ日時 2025-03-20 20:50:50
合計ジャッジ時間 3,595 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 39 WA * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

def find_r(N, E):
    if E == 0:
        return 0

    MOD = 5 ** E
    N_mod = N % MOD

    # Check quadratic residue mod 5
    residue_mod5 = N_mod % 5
    if residue_mod5 not in {0, 1, 4}:
        return None

    # Find initial solutions modulo 5
    if residue_mod5 == 0:
        solutions = [0]
    elif residue_mod5 == 1:
        solutions = [1, 4]
    else:  # residue_mod5 == 4 (which is 2^2 mod 5)
        solutions = [2, 3]

    current_e = 1
    while current_e < E:
        next_e = current_e + 1
        new_solutions = []
        power = 5 ** current_e

        for s in solutions:
            m = (s ** 2 - N_mod) // power

            if s % 5 != 0:
                two_a = (2 * s) % 5
                inv_two_a = pow(two_a, -1, 5)
                t = (-m % 5) * inv_two_a % 5
                new_s = s + t * power
                new_s = new_s % (5 ** next_e)
                new_solutions.append(new_s)
                new_solutions.append((5 ** next_e - new_s) % (5 ** next_e))
            else:
                if N_mod % (5 ** next_e) == 0:
                    new_solutions.append(0)
                    new_solutions.append(5 ** next_e)

        solutions = list(set(new_solutions))
        current_e += 1

    MIN_R = - (1 << 29)
    MAX_R = (1 << 29)

    for s in solutions:
        s_val = s % MOD
        for k in [0, -1, 1]:
            candidate = s_val + k * MOD
            if MIN_R <= candidate <= MAX_R:
                return candidate
        # Check some more possible k's near the edges
        lower_k = (MIN_R - s_val) // MOD
        upper_k = (MAX_R - s_val) // MOD
        for k in [lower_k - 1, lower_k, lower_k + 1, upper_k - 1, upper_k, upper_k + 1]:
            candidate = s_val + k * MOD
            if MIN_R <= candidate <= MAX_R:
                return candidate

    return None

# Read input
N = int(input())
E = int(input())

if E < 0 or E > 13:
    print("NaN")
else:
    if E == 0:
        print(0)
    else:
        r = find_r(N, E)
        if r is not None:
            # Verify that the candidate meets the condition (double-check)
            delta = N - (r ** 2)
            if delta == 0:
                print(r)
            else:
                count = 0
                while delta % 5 == 0:
                    count += 1
                    delta = delta // 5
                if count >= E:
                    print(r)
                else:
                    print("NaN")
        else:
            print("NaN")
0