結果
問題 | No.313 π |
ユーザー |
![]() |
提出日時 | 2015-12-06 00:04:17 |
言語 | PyPy2 (7.3.15) |
結果 |
AC
|
実行時間 | 726 ms / 5,000 ms |
コード長 | 4,696 bytes |
コンパイル時間 | 843 ms |
コンパイル使用メモリ | 77,056 KB |
実行使用メモリ | 114,688 KB |
最終ジャッジ日時 | 2024-09-14 14:33:33 |
合計ジャッジ時間 | 27,880 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 32 |
ソースコード
import sysimport mathfrom math import sqrtdef isqrt(n):if n <= 0:return 0x = int(sqrt(n) * (1 + 1e-12))while True:y = (x + n // x) >> 1if y >= x:return xx = ydef fast_str(N):def rec(N, e, zerofill=False):if e <= 10:if not zerofill:strs.append(str(N))else:strs.append("%0*d" % (1 << (e + 1), N))else:shamt = 1 << eq, r = fast_divmod(N >> shamt, fives[e])r = (r << shamt) | (N & masks[e])if zerofill or q:rec(q, e - 1, zerofill)rec(r, e - 1, True)else:rec(r, e - 1, zerofill)strs = []if N < 0:N = -Nstrs.append("-")fives = []masks = []five = 5mask = 1e = 0while 1:shamt = 1 << eif (five << shamt) > N:breakfives.append(five)masks.append(mask)if (five.bit_length() + shamt) * 2 - 1 > N.bit_length():breake += 1five *= fivemask |= mask << shamtrec(N, e)return "".join(strs)def fast_divmod(a, b):"""Burnikel & Ziegler"""DIVMOD_THRESHOLD = 8000def _pack(pack, shamt):size = len(pack)while size > 1:npack = []for i in range(0, size - 1, 2):npack.append(pack[i] | (pack[i+1] << shamt))if size & 1:npack.append(pack[-1])pack = npacksize = (size + 1) >> 1shamt <<= 1return pack[0]def _unpack(M, size, shamt):needed_sizes = []s = sizewhile s > 1:needed_sizes.append(s)s = (s + 1) >> 1ret = [M]for needed_size in needed_sizes[::-1]:mask = (1 << shamt) - 1nret = []for c in ret:nret.append(c & mask)nret.append(c >> shamt)ret = nret[:needed_size]shamt >>= 1return retdef _div32(a21, a0, b, b1, b0, n):if (a21 >> n) >= b1:q, r = (1 << n) - 1, a21 - (b1 << n) + b1else:q, r = _div21(a21, b1, n)r = ((r << n) | a0) - q * b0while r < 0:q -= 1r += breturn q, rdef _div21(a, b, n):if a < b:return (0, a)if n <= DIVMOD_THRESHOLD:return divmod(a, b)odd = n & 1if odd:a, b, n = a << 1, b << 1, n + 1nh = n >> 1mask = (1 << nh) - 1b1, b0 = b >> nh, b & maskq1, r = _div32(a >> n, (a >> nh) & mask, b, b1, b0, nh)q0, r = _div32(r, a & mask, b, b1, b0, nh)if odd:r >>= 1return (q1 << nh) | q0, rif a < b:return (0, a)m = a.bit_length()n = b.bit_length()if n <= DIVMOD_THRESHOLD:return divmod(a, b)nqs = m // na_blocks = _unpack(a, nqs + 1, (n << (nqs.bit_length() - 1)))qs = []r = a_blocks[-1]for i in range(nqs - 1, -1, -1):q, r = _div21((r << n) | a_blocks[i], b, n)qs.append(q)q = _pack(qs[::-1], n)return q, rdef fast_isqrt(a, threshold=1024):"""GMP Karatsuba Square Root"""def _isqrt(a):if a < threshold:r = isqrt(a)return r, a - r * rn = a.bit_length()adjusted = ((n - 1) & 2) == 0if adjusted:a <<= 2n += 2nq = (n + 1) >> 2nh = nq << 1mask = (1 << nh) - 1ah, al = a >> nh, a & maskmask >>= nqa1, a0 = al >> nq, al & masks1, r1 = _isqrt(ah)q, u = fast_divmod((r1 << nq) + a1, s1 << 1)s = (s1 << nq) + qr = (u << nq) + a0 - q * qif r < 0:r = r + (s << 1) - 1s -= 1if adjusted:r >>= 2if s & 1:s >>= 1r += s + 1else:s >>= 1return s, rreturn _isqrt(a)[0]def pi_chudnovsky_bs(digits):# (c) Nick Craig-Wooddef bs(a, b):if b - a == 1:if a == 0:Pab = Qab = 1else:Pab = (6 * a - 5) * (2 * a - 1) * (6 * a - 1)Qab = a * a * a * C3_OVER_24Tab = Pab * (13591409 + 545140134 * a)if a & 1:Tab = -Tabelse:m = (a + b) // 2Pam, Qam, Tam = bs(a, m)Pmb, Qmb, Tmb = bs(m, b)Pab = Pam * PmbQab = Qam * QmbTab = Qmb * Tam + Pam * Tmbreturn Pab, Qab, TabC = 640320C3_OVER_24 = C ** 3 // 24DIGITS_PER_TERM = math.log10(C3_OVER_24 / 72.)N = int(digits / DIGITS_PER_TERM + 1)_, Q, T = bs(0, N)shamt = 0# prec = int(digits * 3.3219280948873626)# shamt = Q.bit_length() - precnumer = (Q >> shamt) * 426880 * fast_isqrt(10005 * 100 ** digits)denom = T >> shamtreturn fast_divmod(numer, denom)[0]def prob313():rl = sys.stdin.readlinest = pi_chudnovsky_bs(200000)s = fast_str(st)s = s[0:1] + "." + s[1:]A = rl().rstrip()for a, b in zip(A, s):if a != b:print("%s %s" % (a, b))breakprob313()