問題一覧 > 通常問題

No.3156 Count That Day's N

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 112
作問者 : tatesoto / テスター : TKTYI みうね jastaway kencho fluorine kmmtkm butsurizuki
1 ProblemId : 12232 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2025-05-23 19:00:57

問題文

正の整数 $K$, $N$ が与えられます。
正の整数 $n$ が次の条件を満たすとき、$n$ をよい数といいます。

  • 正の整数 $x, y, z$ を用いて、$n = K z^2 = x^6 + y^4$ と表される。
$N$ 以下の正の整数のうち、よい数がいくつあるか求めてください。

制約

  • $1 \le K \le N \le 10^{15}$
  • 入力は全て整数

入力

入力は以下の形式で標準入力から与えられます。

$K\ N$

出力

答えを出力してください。 最後に改行してください。

サンプル

サンプル1
入力
9 10000
出力
1

この入力ケースにおいて、$n$ がよい数である条件は、 「正の整数 $x, y, z$ を用いて、$n = 9z^2 = x^6 + y^4$ と表せる」ことです。
$N = 10000$ 以下の正の整数のうち、よい数であるのは $2025\ (= 9\cdot 15^2 = 3^6 + 6^4)$ だけであるため、$1$ を出力します。

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

サンプル3
入力
3 1000000000000000
出力
0

入力値が 32bit 整数型に収まらないことがあります。

サンプル4
入力
9 1000000000000000
出力
43

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