結果

問題 No.1200 お菓子配り-3
ユーザー 👑 KazunKazun
提出日時 2021-02-04 23:13:03
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 496 ms / 4,000 ms
コード長 2,977 bytes
コンパイル時間 428 ms
コンパイル使用メモリ 82,212 KB
実行使用メモリ 79,232 KB
最終ジャッジ日時 2024-07-01 04:25:37
合計ジャッジ時間 8,537 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 40 ms
54,240 KB
testcase_01 AC 40 ms
54,140 KB
testcase_02 AC 48 ms
60,952 KB
testcase_03 AC 44 ms
56,556 KB
testcase_04 AC 48 ms
57,472 KB
testcase_05 AC 50 ms
62,772 KB
testcase_06 AC 45 ms
55,408 KB
testcase_07 AC 79 ms
74,564 KB
testcase_08 AC 91 ms
77,492 KB
testcase_09 AC 74 ms
71,160 KB
testcase_10 AC 77 ms
73,860 KB
testcase_11 AC 76 ms
72,856 KB
testcase_12 AC 189 ms
78,804 KB
testcase_13 AC 187 ms
78,572 KB
testcase_14 AC 193 ms
78,304 KB
testcase_15 AC 214 ms
78,752 KB
testcase_16 AC 197 ms
79,020 KB
testcase_17 AC 278 ms
78,964 KB
testcase_18 AC 296 ms
79,000 KB
testcase_19 AC 206 ms
78,636 KB
testcase_20 AC 389 ms
79,144 KB
testcase_21 AC 388 ms
79,224 KB
testcase_22 AC 410 ms
78,764 KB
testcase_23 AC 388 ms
78,492 KB
testcase_24 AC 378 ms
79,032 KB
testcase_25 AC 377 ms
79,092 KB
testcase_26 AC 397 ms
79,232 KB
testcase_27 AC 37 ms
53,600 KB
testcase_28 AC 496 ms
78,052 KB
testcase_29 AC 401 ms
78,816 KB
testcase_30 AC 402 ms
78,996 KB
testcase_31 AC 39 ms
53,424 KB
testcase_32 AC 38 ms
52,868 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