問題一覧 > 通常問題

No.1383 Numbers of Product

レベル : / AI推定難易度 : 1900 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 30
作問者 : 蜜蜂 / テスター : Mitarushi
お気に入りにしたユーザー ProblemId : 5644 / 自分の提出
問題文最終更新日: 2021-03-23 18:37:22
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
灘高入試コンテスト2021 (順位表) の他の問題:

Problem Statement

You are given integers $\ N,K,M\ $.

For an integer $\ X\ $ greater than or equal to $\ 1\ $, define $\ f(X)\ $ as follows.

  • The number of pairs $\ (A,B)\ $ of integers greater than or equal to $\ 1\ $ satisfying $A(A+K)(A+2K) \cdots\ (A+BK)=X\ $

For example, when $\ K=1\ $, we have $\ f(12)=1\ $. When $\ (A,B)=(3,1)\ $, we get $\ A(A+K)(A+2K) \cdots\ (A+BK)=3(3+1)=12\ $, which satisfies the condition.

Consider the integers $\ X\ $ between $1\ $ and $\ N\ $, inclusive, such that $\ f(X)=M\ $. Find the number of such $\ X\ $.

Input

$N\ K\ M$

  • $1 \leq N,K,M \leq 10^{18}$
  • All input values are integers.

Output

Given $N,K,M\ $, consider the integers $\ X\ $ between $\ 1\ $ and $\ N\ $, inclusive, such that $\ f(X)=M\ $. Output the number of such $\ X\ $, followed by a newline.

Sample

Sample 1
Input
6 1 1
Output
1

Consider $\ f(X)\ $ for the integers between $\ 1\ $ and $\ N\ $, inclusive, and such that $\ f(X) \geq 1\ $, denoted by $\ X\ $.

・$\ f(2)=1\ $. $\ (A,B)=(1,1)\ $ satisfies the condition.
・$\ f(6)=2\ $. $\ (A,B)=(2,1),(1,2)\ $ satisfy the condition.

Therefore, the only $\ X\ $ between $\ 1\ $ and $\ N\ $, inclusive, such that $\ f(X)=1\ $ is $\ 2\ $.

Sample 2
Input
1 1 1000000000000000000
Output
0

The answer may be $\ 0\ $.

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