結果

問題 No.3365 Prefix and Suffix X
コンテスト
ユーザー n_bitand_n_per_3
提出日時 2025-11-17 22:58:25
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 909 ms / 2,000 ms
コード長 1,681 bytes
コンパイル時間 195 ms
コンパイル使用メモリ 82,568 KB
実行使用メモリ 77,936 KB
最終ジャッジ日時 2025-11-17 22:58:52
合計ジャッジ時間 26,793 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

import math

def inv(a, m):
    """法 m における a の逆元
    """

    r0, r1 = m, a
    x0, x1 = 0, 1

    while r1 != 0:
        q = r0 // r1
        r0, r1 = r1, r0 - q * r1
        x0, x1 = x1, x0 - q * x1

    # ここでもし r_0 != 1 ならエラー処理をすべき

    if x0 < 0:
        x0 += m

    return x0

T = int(input())

for _ in range(T):
    X,M = input().split()
    M = int(M)
    if len(X) == 3:
        if X[0] == X[2]:
            res = int(X[0]+X[1]+X[0]+X[1]+X[0])
            if res % M == 0:
                print(res)
                continue
        if X[0] == X[1] == X[2]:
            res = int(X)
            if res % M == 0:
                print(res)
                continue
            res = int(X[0]*4)
            if res % M == 0:
                print(res)
                continue
    elif len(X) == 2:
        if X[0] == X[1]:
            res = int(X)
            if res % M == 0:
                print(res)
                continue
            res = int(X[0]*3)
            if res % M == 0:
                print(res)
                continue
    else:
        res = int(X)
        if res % M == 0:
            print(res)
            continue
            
    # 意味のないコメントアウト
    x = int(X)
    l = len(X)
    ans = -1
    for k in range(2*l,19):
        a = -x*(1+10**(k-l))
        a %= M
        g = math.gcd(10**l,M)
        if a % g != 0:
            continue
        M_ = M//g
        c_0 = (a//g)*inv(10**l//g,M_)
        L = (-c_0-1)//M_ + 1
        U = (10**(k-2*l)-c_0-1)//M_ + 1
        if L != U:
            ans = x * 10**(k-l) + (c_0+L*M_) * 10**l + x
            break
    print(ans)
0