問題一覧 > 通常問題

No.473 和と積の和

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 54
作問者 : ctyl_0 / テスター : 🍡yurahuna
6 ProblemId : 1437 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2016-12-23 01:33:27

問題文

N(≥2)個の正整数からなる集合Sを考えます。 Sから2つの整数a,b∈Sを選んで取り除き、代わりにa+b+abを集合Sに加えるという操作を、Sの要素数が1になるまで繰り返します。 このとき、最後に残ったSの要素がXとなることがある集合Sの個数Mを答えて下さい。

訂正(2016/12/23 0:15)：この問題文でいう集合とは、数の重複を許しても良い多重集合(multiset)のことです。申し訳ありません。

入力

N X

N,Xは以下の条件を満たす正整数です。
2≤N≤100
1≤X≤109

出力

M

Sの要素の並べ替えでつくられる集合は元の集合と同じとみなします。例えば、S={2,2,3}とS={3,2,2}は集合として等しいので、1通りとみなします。 最後に改行してください。
出力される個数Mは、0≤M≤2×105を満たすことが保証されています。
Writer解では、C++14(70ms), Python3(1900ms), PyPy3(630ms)で正解しています。

サンプル

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

条件を満たすSは、{1,7},{3,3}の2通りです。
S={1,7}の場合は、1,7を選ぶと1+7+1×7=15となり、15を作ることができます。
S={3,3}の場合も、3,3を選ぶと3+3+3×3=15となり、15を作ることができます。

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

条件を満たすSは、{2,2,2}の1通りです。
1回目の操作で2,2をSから取り除き、2+2+2×2=8をSに入れます。このとき、S={2,8}となっています。
2回目の操作で2,8をSから取り除き、2+8+2×8=26となり、条件を満たします。

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

条件を満たす集合Sは存在しないことがあります。

サンプル4
入力
6 147026879
出力
147520

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