結果

問題 No.1200 お菓子配り-3
ユーザー 👑 KazunKazun
提出日時 2021-02-04 23:29:25
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 604 ms / 4,000 ms
コード長 3,091 bytes
コンパイル時間 371 ms
コンパイル使用メモリ 87,112 KB
実行使用メモリ 81,516 KB
最終ジャッジ日時 2023-09-13 20:03:33
合計ジャッジ時間 10,209 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 72 ms
71,764 KB
testcase_01 AC 72 ms
71,648 KB
testcase_02 AC 94 ms
76,328 KB
testcase_03 AC 91 ms
72,292 KB
testcase_04 AC 91 ms
72,168 KB
testcase_05 AC 95 ms
76,816 KB
testcase_06 AC 91 ms
72,560 KB
testcase_07 AC 119 ms
78,572 KB
testcase_08 AC 125 ms
78,364 KB
testcase_09 AC 120 ms
78,256 KB
testcase_10 AC 120 ms
78,124 KB
testcase_11 AC 123 ms
78,480 KB
testcase_12 AC 224 ms
79,804 KB
testcase_13 AC 240 ms
80,204 KB
testcase_14 AC 234 ms
79,900 KB
testcase_15 AC 262 ms
80,368 KB
testcase_16 AC 223 ms
80,596 KB
testcase_17 AC 321 ms
80,976 KB
testcase_18 AC 321 ms
81,004 KB
testcase_19 AC 237 ms
80,008 KB
testcase_20 AC 404 ms
81,168 KB
testcase_21 AC 416 ms
81,516 KB
testcase_22 AC 437 ms
80,716 KB
testcase_23 AC 422 ms
80,940 KB
testcase_24 AC 416 ms
80,736 KB
testcase_25 AC 403 ms
80,188 KB
testcase_26 AC 427 ms
80,800 KB
testcase_27 AC 71 ms
71,760 KB
testcase_28 AC 604 ms
80,772 KB
testcase_29 AC 423 ms
81,124 KB
testcase_30 AC 431 ms
80,908 KB
testcase_31 AC 75 ms
71,528 KB
testcase_32 AC 74 ms
71,472 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#Miller-Rabinの素数判定法
def Miller_Rabin_Primality_Test(N,Times=20):
    """Miller-Rabinによる整数Nの素数判定を行う.

    N:整数
    ※:Trueは正確にはProbably Trueである(Falseは確定False).
    """
    from random import randint as ri

    if N==2:
        return True

    if N==1 or N%2==0:
        return False

    q=N-1
    k=0
    while q&1==0:
        k+=1
        q>>=1

    for _ in range(Times):
        m=ri(2,N-1)
        y=pow(m,q,N)
        if y==1:
            continue

        flag=True
        for i in range(k):
            if (y+1)%N==0:
                flag=False
                break

            y*=y
            y%=N

        if flag:
            return False
    return True

#ポラード・ローアルゴリズムによって素因数を発見する
#参考元:https://judge.yosupo.jp/submission/6131
def Find_Factor_Rho(N):
    from math import gcd
    m=1<<(N.bit_length()//8+1)

    for c in range(1,99):
        f=lambda x:(x*x+c)%N
        y,r,q,g=2,1,1,1
        while g==1:
            x=y
            for i in range(r):
                y=f(y)
            k=0
            while k<r and g==1:
                for i in range(min(m, r - k)):
                    y=f(y)
                    q=q*abs(x - y)%N
                g=gcd(q,N)
                k+=m
            r <<=1

        if g<N:
            if Miller_Rabin_Primality_Test(g):
                return g
            elif Miller_Rabin_Primality_Test(N//g):
                return N//g

#ポラード・ローアルゴリズムによる素因数分解
#参考元:https://judge.yosupo.jp/submission/6131
def Pollard_Rho_Prime_Factorization(N):
    I=2
    res=[]
    while I*I<=N:
        if N%I==0:
            k=0
            while N%I==0:
                k+=1
                N//=I
            res.append([I,k])

        I+=1+(I%2)

        if I!=101 or N<2**20:
            continue

        while N>1:
            if Miller_Rabin_Primality_Test(N):
                res.append([N,1])
                N=1
            else:
                j=Find_Factor_Rho(N)
                k=0
                while N%j==0:
                    N//=j
                    k+=1
                res.append([j,k])
    if N>1:
        res.append([N,1])
    res.sort(key=lambda x:x[0])
    return res
#====================================
import sys
input=sys.stdin.readline
write=sys.stdout.write
from itertools import product
S=int(input())
L=[0]*S

for i in range(S):
    X,Y=map(int,input().split())

    P=Pollard_Rho_Prime_Factorization(X+Y)
    T=[]
    for p,e in P:
        V=[1]
        x=1
        for _ in range(e):
            x*=p
            V.append(x)
        T.append(V)

    K=0
    for t in product(*T):
        d=1
        for k in range(len(T)):
            d*=t[k]

        if d==1:
            continue
        elif d==2:
            if X==Y:
                K+=X-1
        else:
            A=d-1
            B2=A*X-Y
            C2=-X+A*Y

            if B2>0 and C2>0 and B2%(A*A-1)==C2%(A*A-1)==0:
                K+=1
    L[i]=K

write("\n".join(map(str,L)))
0