結果

問題 No.3036 Nauclhlt型文字列
コンテスト
ユーザー lam6er
提出日時 2025-04-15 23:28:22
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 1,228 bytes
コンパイル時間 205 ms
コンパイル使用メモリ 82,068 KB
実行使用メモリ 67,284 KB
最終ジャッジ日時 2025-04-15 23:29:48
合計ジャッジ時間 1,734 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample RE * 3
other RE * 15
権限があれば一括ダウンロードができます

ソースコード

diff # 

one = True
zero = one - one
two = one + one
three = two + one
four = three + one
five = four + one
six = five + one
seven = six + one
eight = seven + one
nine = eight + one
ten = nine + one
mod = (ten ** nine) + seven

def add(x, y):
    x += y
    if x >= mod:
        x -= mod
    return x

def subtract(x, y):
    x -= y
    if x < zero:
        x += mod
    return x

def multiply(a, b):
    a = add(a, zero)
    b = add(b, zero)
    res = zero
    while b > zero:
        if b & one:
            res = add(res, a)
        a = add(a, a)
        b = b >> one
    return res

def lucas(n):
    if n == zero:
        return two
    a, b, s = two, one, one
    mask = one << (n.bit_length() - one)
    while mask > zero:
        a_sq = multiply(a, a)
        two_s = multiply(two, s)
        c = subtract(a_sq, two_s)
        ab = multiply(a, b)
        d = subtract(ab, s)
        new_a, new_b = c, d
        new_s = one
        if n & mask:
            new_a = d
            new_b = add(c, d)
            new_s = subtract(zero, one)
        a, b, s = new_a, new_b, new_s
        mask = mask >> one
    return a

import sys

T = int(sys.stdin.readline())
for _ in range(T):
    n = int(sys.stdin.readline())
    print(lucas(n))
0