結果

問題 No.1200 お菓子配り-3
ユーザー 👑 KazunKazun
提出日時 2021-02-04 23:13:03
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 562 ms / 4,000 ms
コード長 2,977 bytes
コンパイル時間 381 ms
コンパイル使用メモリ 87,360 KB
実行使用メモリ 80,980 KB
最終ジャッジ日時 2023-09-13 19:53:08
合計ジャッジ時間 11,526 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 76 ms
71,196 KB
testcase_01 AC 77 ms
71,336 KB
testcase_02 AC 102 ms
76,400 KB
testcase_03 AC 100 ms
72,104 KB
testcase_04 AC 96 ms
72,140 KB
testcase_05 AC 101 ms
76,680 KB
testcase_06 AC 97 ms
72,432 KB
testcase_07 AC 130 ms
78,520 KB
testcase_08 AC 137 ms
78,616 KB
testcase_09 AC 128 ms
78,248 KB
testcase_10 AC 128 ms
78,704 KB
testcase_11 AC 129 ms
78,336 KB
testcase_12 AC 241 ms
80,468 KB
testcase_13 AC 242 ms
80,188 KB
testcase_14 AC 246 ms
80,376 KB
testcase_15 AC 241 ms
80,212 KB
testcase_16 AC 247 ms
80,624 KB
testcase_17 AC 318 ms
80,800 KB
testcase_18 AC 355 ms
80,848 KB
testcase_19 AC 259 ms
80,236 KB
testcase_20 AC 471 ms
80,740 KB
testcase_21 AC 457 ms
80,832 KB
testcase_22 AC 488 ms
80,580 KB
testcase_23 AC 443 ms
80,584 KB
testcase_24 AC 424 ms
80,160 KB
testcase_25 AC 438 ms
80,656 KB
testcase_26 AC 464 ms
80,980 KB
testcase_27 AC 75 ms
71,400 KB
testcase_28 AC 562 ms
80,448 KB
testcase_29 AC 459 ms
80,580 KB
testcase_30 AC 461 ms
80,356 KB
testcase_31 AC 75 ms
71,508 KB
testcase_32 AC 75 ms
71,600 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
#====================================
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)
    A=[range(e+1) for _,e in P]
    D=[]

    for t in product(*A):
        d=1
        for k in range(len(A)):
            d*=P[k][0]**t[k]
        D.append(d)

    K=0
    for d in D:
        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

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