結果

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

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 39 ms
53,132 KB
testcase_01 AC 38 ms
53,080 KB
testcase_02 AC 49 ms
61,640 KB
testcase_03 AC 45 ms
56,736 KB
testcase_04 AC 44 ms
56,160 KB
testcase_05 AC 47 ms
62,484 KB
testcase_06 AC 44 ms
56,036 KB
testcase_07 AC 72 ms
71,704 KB
testcase_08 AC 77 ms
74,944 KB
testcase_09 AC 70 ms
70,832 KB
testcase_10 AC 74 ms
73,264 KB
testcase_11 AC 74 ms
72,816 KB
testcase_12 AC 179 ms
78,108 KB
testcase_13 AC 184 ms
78,288 KB
testcase_14 AC 179 ms
78,228 KB
testcase_15 AC 174 ms
78,388 KB
testcase_16 AC 187 ms
78,956 KB
testcase_17 AC 255 ms
79,220 KB
testcase_18 AC 279 ms
79,344 KB
testcase_19 AC 194 ms
78,928 KB
testcase_20 AC 371 ms
79,112 KB
testcase_21 AC 382 ms
79,100 KB
testcase_22 AC 403 ms
79,112 KB
testcase_23 AC 371 ms
78,800 KB
testcase_24 AC 380 ms
79,512 KB
testcase_25 AC 366 ms
79,004 KB
testcase_26 AC 413 ms
79,548 KB
testcase_27 AC 39 ms
53,472 KB
testcase_28 AC 544 ms
79,476 KB
testcase_29 AC 407 ms
79,356 KB
testcase_30 AC 403 ms
78,680 KB
testcase_31 AC 40 ms
52,784 KB
testcase_32 AC 39 ms
53,076 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