No.1383 Numbers of Product
タグ : / 解いたユーザー数 28
作問者 :
蜜蜂
/ テスター :
Mitarushi
問題文
整数$\ 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もしくは右上の雲マークをクリックしてアカウントを作成してください。