結果

問題 No.493 とても長い数列と文字列(Long Long Sequence and a String）
ユーザー gew1fw
提出日時 2025-06-12 13:51:32
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,900 bytes
コンパイル時間 238 ms
コンパイル使用メモリ 82,416 KB
実行使用メモリ 76,308 KB
最終ジャッジ日時 2025-06-12 13:52:50
合計ジャッジ時間 18,298 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 55 TLE * 1 -- * 59
権限があれば一括ダウンロードができます

ソースコード

diff # 

precomputed_lens = {}
current_len = 1
overflow = False
precomputed_lens[1] = (current_len, overflow)
max_precompute = 60

for n in range(2, max_precompute + 1):
    if overflow:
        precomputed_lens[n] = (current_len, overflow)
        continue
    s = len(str(n**2))
    new_len = 2 * current_len + s
    if new_len > 10**18:
        overflow = True
        current_len = 10**18 + 1  # Mark as overflow
    else:
        current_len = new_len
    precomputed_lens[n] = (current_len, overflow)

def get_digit(n, pos):
    while True:
        if n == 1:
            return 1
        if n > max_precompute:
            n -= 1
            continue
        len_prev, overflow_prev = precomputed_lens.get(n-1, (0, False))
        s_n = len(str(n**2))
        if overflow_prev:
            n -= 1
            continue
        if pos <= len_prev:
            n -= 1
        elif pos <= len_prev + s_n:
            num_str = str(n**2)
            return int(num_str[pos - len_prev - 1])
        else:
            pos -= (len_prev + s_n)
            n -= 1

def main():
    import sys
    K, L, R = map(int, sys.stdin.readline().split())
    max_allowed = 10**18
    len_K = 0
    overflow_K = False

    if K in precomputed_lens:
        len_K, overflow_K = precomputed_lens[K]
    else:
        overflow_K = True
        len_K = max_allowed + 1

    if overflow_K:
        if R > max_allowed:
            print(-1)
            return
    else:
        if R > len_K:
            print(-1)
            return

    MOD = 10**9 + 7
    total_sum = 0
    total_product = 1

    for pos in range(L, R + 1):
        d = get_digit(K, pos)
        if d == 0:
            total_sum += 10
            total_product = (total_product * 10) % MOD
        else:
            total_sum += d
            total_product = (total_product * d) % MOD

    print(total_sum, total_product)

if __name__ == "__main__":
    main()
0