結果
問題 | No.2125 Inverse Sum |
ユーザー | FromBooska |
提出日時 | 2023-03-06 16:17:23 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,208 bytes |
コンパイル時間 | 276 ms |
コンパイル使用メモリ | 82,024 KB |
実行使用メモリ | 76,168 KB |
最終ジャッジ日時 | 2024-09-18 01:52:06 |
合計ジャッジ時間 | 24,218 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 17 TLE * 2 WA * 11 |
ソースコード
# 変形してQ*(M+N) = N*M*P# gcd(P, Q)で両辺を割る# もしP=Q=1の場合、M=N=2# それ以外の場合、N,MはQの素因数を持つ、N+MはPの倍数# Qの約数でNを全探索すればいいdef divisors(n):lower_divisors , upper_divisors = [], []i = 1while i*i <= n:if n % i == 0:lower_divisors.append(i)if i != n // i:upper_divisors.append(n//i)i += 1return lower_divisors + upper_divisors[::-1]from math import gcdP, Q = map(int, input().split())g = gcd(P, Q)P = P//gQ = Q//gif P == 1:print(1)print(Q*2, Q*2)else:ans_list = []divs = divisors(Q)for n in divs:if (P*n-Q) != 0 and (n*Q)%(P*n-Q) == 0 and (n*Q)//(P*n-Q) > 0:if Q*(((n*Q)//(P*n-Q))+n) == P*((n*Q)//(P*n-Q))*n:ans_list.append((n, (n*Q)//(P*n-Q)))for k in range(2, 10**7):n_ = n*kif (P*n_-Q) != 0 and (n_*Q)%(P*n_-Q) == 0 and (n_*Q)//(P*n_-Q) > 0:if Q*(((n_*Q)//(P*n_-Q))+n_) == P*((n_*Q)//(P*n_-Q))*n_:ans_list.append((n_, (n_*Q)//(P*n_-Q)))print(len(ans_list))for n, m in ans_list:print(n, m)