結果
問題 | No.303 割れません |
ユーザー | Min_25 |
提出日時 | 2015-11-14 07:33:56 |
言語 | Python2 (2.7.18) |
結果 |
AC
|
実行時間 | 2,296 ms / 10,000 ms |
コード長 | 2,343 bytes |
コンパイル時間 | 438 ms |
コンパイル使用メモリ | 6,616 KB |
実行使用メモリ | 9,048 KB |
最終ジャッジ日時 | 2023-10-11 17:42:14 |
合計ジャッジ時間 | 21,995 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 11 ms
5,828 KB |
testcase_01 | AC | 11 ms
5,832 KB |
testcase_02 | AC | 11 ms
5,888 KB |
testcase_03 | AC | 739 ms
7,340 KB |
testcase_04 | AC | 2,109 ms
9,048 KB |
testcase_05 | AC | 2,097 ms
8,728 KB |
testcase_06 | AC | 2,093 ms
8,908 KB |
testcase_07 | AC | 2,202 ms
8,588 KB |
testcase_08 | AC | 2,283 ms
8,540 KB |
testcase_09 | AC | 2,264 ms
8,460 KB |
testcase_10 | AC | 11 ms
5,928 KB |
testcase_11 | AC | 2,112 ms
9,008 KB |
testcase_12 | AC | 2,296 ms
8,496 KB |
testcase_13 | AC | 1,166 ms
7,804 KB |
testcase_14 | AC | 581 ms
7,036 KB |
testcase_15 | AC | 329 ms
6,792 KB |
testcase_16 | AC | 11 ms
5,988 KB |
ソースコード
def fib(n): if n <= 2: return ((n + 1) >> 1, (n + 2) >> 1) a, b = fib(n >> 1) if n & 1: return (a * a + b * b, b * ((a << 1) + b)) else: return (a * ((b << 1) - a), a * a + b * b) def fast_divmod(N, D, threshold=1<<512): i_prec = 50 if N < threshold or D < (1 << i_prec): return divmod(N, D) if N < D: return (0, N) guard_bits = 3 ilog2_n = N.bit_length() ilog2_d = D.bit_length() ilog2_q = ilog2_n + 1 - ilog2_d n_shamt = ilog2_n - (ilog2_q + guard_bits) d = D >> (ilog2_d - i_prec) reciprocal = int(float(1 << (2 * i_prec)) / float(d)) prec = ilog2_q precs = [] while prec > i_prec: precs.append(prec) prec = (prec >> 1) + guard_bits curr_prec = i_prec for prec in precs[::-1]: if prec >= ilog2_d: d = D lshift = prec - ilog2_d else: d = D >> (ilog2_d - prec) lshift = 0 r = (1 << prec) - (((d * reciprocal) << lshift) >> curr_prec) left = reciprocal << (prec - curr_prec) right = (reciprocal * r) >> curr_prec reciprocal = left + right curr_prec = prec n = N >> n_shamt q = (n * reciprocal) >> (curr_prec + guard_bits + 1) r = N - q * D if r < 0: while r < 0: r += D q -= 1 elif r >= D: while r >= D: r -= D q += 1 return q, r def print_big_integer(N, out, newline=True, beg=0, tens=None): def rec(N, e, zerofill=False): if e <= 10: if not zerofill: out.write("%s" % str(N)[beg:]) else: out.write("%0*d" % (1 << e, N)) else: ten = tens[e-1] q, r = fast_divmod(N, ten) if zerofill or q: rec(q, e - 1, zerofill) rec(r, e - 1, True) else: rec(r, e - 1, zerofill) if N < 0: N = -N out.write("-") if tens is None: tens = [] ten = 10 while ten <= N: tens.append(ten) if ten.bit_length() * 2 - 1 > N.bit_length(): break ten *= ten e = 0 while e < len(tens) and N >= tens[e]: e += 1 rec(N, e) if newline: print("") return def prob303(): import sys n = int(sys.stdin.readline()) if n == 2: print("3") print("INF") else: if n & 1: ans = fib(n)[0] else: a, b = fib(n // 2 - 1) ans = (a * b) << 1 print(n) # print(ans) print_big_integer(ans, sys.stdout) prob303()