結果

問題 No.313 π
コンテスト
ユーザー yuppe19 😺
提出日時 2015-12-06 16:26:36
言語 PyPy2
(7.3.15)
結果
AC  
実行時間 1,384 ms / 5,000 ms
コード長 1,865 bytes
コンパイル時間 1,482 ms
コンパイル使用メモリ 77,192 KB
実行使用メモリ 130,704 KB
最終ジャッジ日時 2024-09-14 15:51:41
合計ジャッジ時間 51,492 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge6
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

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