問題一覧 > 通常問題

No.1383 Numbers of Product

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 26
作問者 : 蜜蜂蜜蜂 / テスター : MitarushiMitarushi
2 ProblemId : 5644 / 出題時の順位表
問題文最終更新日: 2021-02-14 21:06:15

問題文

整数$\ N,K,M\ $が与えられます。

$\ 1\ $以上の整数$\ X\ $について、$\ f(X)\ $を以下のように定義します。

  • $A(A+K)(A+2K) \cdots\ (A+BK)=X\ $を満たすような$\ 1\ $以上の整数からなる組$\ (A,B)\ $の数

例えば$\ K=1\ $のとき、$\ f(12)=1\ $です。$\ (A,B)=(3,1)\ $の時に$\ A(A+K)(A+2K) \cdots\ (A+BK)=3(3+1)=12\ $となり、条件を満たします。

このとき、$1\ $以上$\ N\ $以下の整数$\ X\ $で$\ f(X)=M\ $となるような$\ X\ $の個数を求めてください。

入力

$N\ K\ M$

  • $1 \leq N,K,M \leq 10^{18}$
  • 入力は全て整数

出力

$N,K,M\ $が与えられるので、$\ 1\ $以上$\ N\ $以下の整数$\ X\ $で$\ f(X)=M\ $となるような$\ X\ $の個数を出力し、最後に改行してください。

サンプル

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

$\ 1\ $以上$\ N\ $以下かつ$\ f(X) \geq 1\ $となるような$\ X\ $について$\ f(X)\ $を考えます。

・$\ f(2)=1\ $です。$\ (A,B)=(1,1)\ $が条件を満たします。
・$\ f(6)=2\ $です。$\ (A,B)=(2,1),(1,2)\ $が条件を満たします。

よって、$\ 1\ $以上$\ N\ $以下かつ$\ f(X)=1\ $となるような$\ X\ $は$\ 2\ $のみです。

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

答えが$\ 0\ $になることもあります。

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