問題一覧 > 通常問題

No.2125 Inverse Sum

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 69
作問者 : 遭難者 / テスター : 👑 potato167 とりゐ
5 ProblemId : 6483 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-05-31 10:38:41

問題文

正整数 P,QP,Q が与えられます。

1N+1M=PQ\displaystyle\frac1N+\frac1M=\frac PQ を満たす正整数 (N,M)(N,M) の組を全て求めてください。

制約

  • 1P,Q1091\le P,Q\le 10^9
  • 入力は全て整数
  • 入力

    PP QQ
    

    出力

    以下の形式で出力してください。

    TT
    N1N_1 M1M_1
    \vdots
    NTN_T MTM_T
    ただし、 TT は条件を満たす (N,M)(N,M) の組の個数で、 (Ni,Mi)(N_i,M_i) は条件を満たす組のうち NNii 番目に小さいものです。

    また、制約下ではどの Ni,MiN_i,M_i も 64 bit 整数型に収まることが証明できます。

    サンプル

    サンプル1
    入力
    1 1
    出力
    1
    2 2

    1N+1M=1\displaystyle\frac1N+\frac1M=1 を満たす (N,M)(N,M)(2,2)(2,2) のみです。

    サンプル2
    入力
    6 8
    出力
    2
    2 4
    4 2

    サンプル3
    入力
    9 4
    出力
    0

    条件を満たす (N,M)(N,M) の組が存在しないこともあります。

    提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。