結果

問題 No.313 π
ユーザー yuppe19 😺yuppe19 😺
提出日時 2015-12-06 16:26:36
言語 PyPy2
(7.3.15)
結果
AC  
実行時間 2,868 ms / 5,000 ms
コード長 1,865 bytes
コンパイル時間 1,681 ms
コンパイル使用メモリ 78,024 KB
実行使用メモリ 118,780 KB
最終ジャッジ日時 2023-10-12 17:17:18
合計ジャッジ時間 102,248 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2,816 ms
118,368 KB
testcase_01 AC 2,811 ms
118,052 KB
testcase_02 AC 2,814 ms
118,156 KB
testcase_03 AC 2,817 ms
118,476 KB
testcase_04 AC 2,819 ms
118,156 KB
testcase_05 AC 2,816 ms
118,256 KB
testcase_06 AC 2,818 ms
118,456 KB
testcase_07 AC 2,817 ms
118,256 KB
testcase_08 AC 2,830 ms
118,780 KB
testcase_09 AC 2,828 ms
118,500 KB
testcase_10 AC 2,824 ms
118,116 KB
testcase_11 AC 2,814 ms
118,252 KB
testcase_12 AC 2,818 ms
118,044 KB
testcase_13 AC 2,859 ms
118,208 KB
testcase_14 AC 2,814 ms
118,324 KB
testcase_15 AC 2,805 ms
118,236 KB
testcase_16 AC 2,811 ms
117,632 KB
testcase_17 AC 2,825 ms
118,304 KB
testcase_18 AC 2,823 ms
118,220 KB
testcase_19 AC 2,817 ms
118,432 KB
testcase_20 AC 2,818 ms
118,364 KB
testcase_21 AC 2,817 ms
118,388 KB
testcase_22 AC 2,806 ms
117,664 KB
testcase_23 AC 2,817 ms
118,456 KB
testcase_24 AC 2,815 ms
118,344 KB
testcase_25 AC 2,816 ms
118,364 KB
testcase_26 AC 2,816 ms
118,160 KB
testcase_27 AC 2,821 ms
118,396 KB
testcase_28 AC 2,811 ms
118,220 KB
testcase_29 AC 2,833 ms
118,460 KB
testcase_30 AC 2,868 ms
118,420 KB
testcase_31 AC 2,822 ms
118,468 KB
testcase_32 AC 2,820 ms
118,376 KB
testcase_33 AC 2,821 ms
118,460 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#!/usr/bin/python
# -*- coding: utf-8 -*-
# †
from collections import namedtuple
from math import log10
Tup = namedtuple('Tup', 'p, q, t')

#def isqrt(n):
#    if n < 0:
#        raise ValueError('square root not defined for negative numbers')
#    if n == 0:
#        return 0
#    a, b = divmod(n.bit_length(), 2)
#    x = 1<<(a+b)
#    while True:
#        y = (x + n//x)//2
#        if y >= x:
#            return x
#        x = y

def newtonsqrt(q, n, init):
    x, m, c3 = init, 0, 3
    c3 <<= n
    while m != x:
        m = x
        x *= c3 - ((m * m * q) >> n)
        x >>= n + 1
    return x

def isqrt(s):
    n = s.bit_length()
    b = 8192
    if n & 1:
        b += 1
    x = 1<<(b/2)
    m = n / 6
    while 1:
        w = s >> (n-b)
        x = newtonsqrt(w, b, x)
        y = 2 * m
        if b + y > n:
            break
        b += y
        x <<= m
    x <<= (n-b) / 2
    x = newtonsqrt(s, n, x) * s >> n
    return x

def pi_chudnovsky_bs(digits):
    C = 640320
    C3_OVER_24 = C**3 // 24
    def bs(a, b):
        if b - a == 1:
            if a == 0:
                p = q = 1
            else:
                p = (6*a-5)*(2*a-1)*(6*a-1)
                q = a*a*a*C3_OVER_24
            t = p * (a*545140134 + 13591409)
            if a & 1:
                t = -t
        else:
            m = (a + b) // 2
            am = bs(a, m)
            mb = bs(m, b)
            p = am.p * mb.p
            q = am.q * mb.q
            t = mb.q * am.t + am.p * mb.t
        return Tup(p, q, t)
    DIGITS_PER_TERM = log10(C3_OVER_24/6/2/6)
    n = int(digits/DIGITS_PER_TERM + 1)
    _, Q, T = bs(0, n)
    sq = isqrt(10005 * 10**(2*digits))
    return (Q*426880*sq) // T

N = 200000
res = str(pi_chudnovsky_bs(N))
S = raw_input().replace('.', '')
for i in xrange(N, -1, -1):
    if S[i] != res[i]:
        print S[i], res[i]
        break
0