結果

問題 No.8036 Restricted Lucas (Easy)
ユーザー toriaezuAC
提出日時 2018-04-02 17:45:27
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 29 ms / 2,000 ms
コード長 1,797 bytes
コンパイル時間 629 ms
コンパイル使用メモリ 67,556 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-06-26 06:41:20
合計ジャッジ時間 1,313 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 6
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <iostream>
using namespace std;
enum {
    Ca, Cb, Cc, Cd, Ce, Cf, Cg, Ch, Ci, Cj, Ck
};
using ull = unsigned long long;
constexpr ull Adder(ull a, ull b, ull carry) {
    ull ret = Ca;
    for (ull mask = Cb; mask != Ca; mask <<= Cb) {
        ull am = (a & mask);
        ull bm = (b & mask);
        ull rm = am ^ bm ^ carry;
        ret |= rm;
        carry = (am & bm | am & carry | bm & carry) << Cb;
    }
    return ret;
}
constexpr ull Plus(ull a, ull b) {
    return Adder(a, b, Ca);
}
constexpr ull Minus(ull a, ull b) {
    return Adder(a, ~b, Cb);
}
constexpr ull Mul(ull a, ull b) {
    ull ret = Ca;
    for (ull mask = Cb; mask != Ca; mask <<= Cb, a <<= Cb) {
        ull bm = (b & mask);
        if (bm) {
            ret = Plus(ret, a);
        }
    }
    return ret;
}
constexpr ull Pow(ull base, ull exp) {
    if (exp == Ca) return Cb;
    return Mul(base, Pow(base, Minus(exp, Cb)));
}
ull Mod(ull dividend) {
    constexpr ull Modulo = Plus(Pow(Ck, Cj), Ch);
    constexpr ull Shift = Minus(Pow(Cg, Cc), Cc);
    for (ull divisor = Modulo << Shift; divisor >= Modulo; divisor >>= Cb) {
        if (dividend >= divisor) {
            dividend = Minus(dividend, divisor);
        }
    }
    return dividend;
}
struct Hoge {
    ull k;
    ull l;
};
Hoge FormHoge(ull i) {
    if (i == Ca) return Hoge{ Cb, Ca };
    if (i == Cb) return Hoge{ Ca, Cb };
    ull half = i >> Cb;
    if ((half << Cb) != i) {
        Hoge sub = FormHoge(Minus(i, Cb));
        return Hoge{ sub.l, Mod(Plus(sub.k, sub.l)) };
    }
    Hoge tmp = FormHoge(half);
    ull new_k = Mod(Plus(Mul(tmp.k, tmp.k), Mul(tmp.l, tmp.l)));
    ull new_l = Mod(Mul(tmp.l, Plus(tmp.k << Cb, tmp.l)));
    return Hoge{ new_k, new_l };
}
ull Lucas(ull i) {
    Hoge hoge = FormHoge(i);
    return Mod(Plus(hoge.k << Cb, hoge.l));
}
int main() {
    ull T;
    cin >> T;
    for (ull i = Ca; i < T; i = Plus(i, Cb)) {
        ull a;
        cin >> a;
        cout << Lucas(a) << endl;
    }
    return Ca;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0