結果

問題 No.3037 Restricted Lucas (Hard)
ユーザー toriaezuACtoriaezuAC
提出日時 2018-04-02 17:45:55
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 5 ms / 2,000 ms
コード長 1,796 bytes
コンパイル時間 634 ms
コンパイル使用メモリ 66,048 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-06-26 06:41:23
合計ジャッジ時間 1,160 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 3 ms
5,376 KB
testcase_02 AC 5 ms
5,376 KB
testcase_03 AC 4 ms
5,376 KB
testcase_04 AC 5 ms
5,376 KB
testcase_05 AC 4 ms
5,376 KB
testcase_06 AC 5 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

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;
}
0