結果

問題 No.2125 Inverse Sum
コンテスト
ユーザー flippergo
提出日時 2026-09-17 09:12:47
言語 PyPy3
(7.3.23 + ACL)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 205 ms / 2,000 ms
+ 495µs
コード長 1,152 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 76 ms
コンパイル使用メモリ 81,152 KB
実行使用メモリ 92,076 KB
最終ジャッジ日時 2026-09-17 09:13:35
合計ジャッジ時間 4,198 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

P,Q = map(int,input().split())
def gcd(a,b):
    if b==0:return a
    return gcd(b,a%b)
d = gcd(P,Q)
P //= d
Q //= d
A = list(range(10**5+1))
for i in range(2,10**5+1):
    if i*i>10**5:break
    for j in range(i*i,10**5+1,i):
        A[j] = A[i]
B = []
for i in range(2,10**5+1):
    if A[i]==i:
        B.append(i)
D = {}
x = Q
for p in B:
    if x==1:break
    while x%p==0:
        D[p] = D.get(p,0)+1
        x //= p
if x>1:
    D[x] = 1
def dfs(i,j,C,n):
    global F
    if i==len(C):
        F[j].append(n)
        return
    for k in range(D[C[i]]+1):
        n *= pow(C[i],k)
        dfs(i+1,j,C,n)
        n //= pow(C[i],k)
    return
E = list(D.items())  
J = len(D)
ans = set()
for i in range(1<<J):
    C1 = []
    C2 = []
    for k in range(J):
        if (i>>k)&1:
            C1.append(E[k][0])
        else:
            C2.append(E[k][0])
    F = [[],[]]
    dfs(0,0,C1,1)
    dfs(0,1,C2,1)
    for n in F[0]:
        for m in F[1]:
            if (Q//n+Q//m)%P==0:
                d = (Q//n+Q//m)//P
                ans.add((n*d,m*d))
ans = list(ans)
ans = sorted(ans,key=lambda x:x[0])
print(len(ans))
for N,M in ans:
    print(N,M)
0