結果

問題 No.313 π
ユーザー yuppe19 😺yuppe19 😺
提出日時 2015-12-06 16:28:07
言語 PyPy2
(7.3.15)
結果
WA  
実行時間 -
コード長 1,865 bytes
コンパイル時間 1,663 ms
コンパイル使用メモリ 76,760 KB
実行使用メモリ 93,724 KB
最終ジャッジ日時 2023-10-12 16:46:01
合計ジャッジ時間 25,929 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 650 ms
92,932 KB
testcase_01 WA -
testcase_02 AC 661 ms
93,140 KB
testcase_03 AC 659 ms
93,724 KB
testcase_04 AC 655 ms
92,916 KB
testcase_05 AC 649 ms
93,544 KB
testcase_06 AC 653 ms
92,936 KB
testcase_07 AC 646 ms
93,220 KB
testcase_08 AC 653 ms
92,932 KB
testcase_09 AC 651 ms
93,136 KB
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 AC 656 ms
92,976 KB
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 AC 664 ms
92,936 KB
testcase_25 AC 664 ms
93,528 KB
testcase_26 WA -
testcase_27 WA -
testcase_28 AC 664 ms
92,976 KB
testcase_29 WA -
testcase_30 AC 660 ms
93,408 KB
testcase_31 AC 656 ms
92,932 KB
testcase_32 WA -
testcase_33 AC 662 ms
92,964 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 = 100000
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