結果

問題 No.2125 Inverse Sum
コンテスト
ユーザー flippergo
提出日時 2026-09-17 08:51:28
言語 PyPy3
(7.3.23 + ACL)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
WA  
実行時間 -
コード長 1,013 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 90 ms
コンパイル使用メモリ 81,152 KB
実行使用メモリ 309,400 KB
最終ジャッジ日時 2026-09-17 08:51:36
合計ジャッジ時間 6,283 ms
ジャッジサーバーID
（参考情報） 		judge1_1 / judge3_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 1 WA * 1 TLE * 1 -- * 27
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

P,Q = map(int,input().split())
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:
    while x%p==0:
        x = x//p
        D[x] = D.get(x,0)+1
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)
print(len(ans))
for N,M in ans:
    print(N,M)
0