問題一覧 > 通常問題

No.1567 Integer Coefficient Equation

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 15
作問者 : PCTprobabilityPCTprobability / テスター : blackyukiblackyuki
1 ProblemId : 6288 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-06-26 15:18:34

問題文

$L$ 以上 $R$ 以下の整数 $k$ の内、以下の条件を満たすものの個数を求めてください。(13:34 正整数 -> 整数に修正)

  • 整数係数多項式 $f(x)$ の内、方程式 $f(x) = P$ の異なる整数解が $5$ 個以上あり、かつ $f(x) = k$ が整数解をもつものが存在する。

$T$ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

入力

$T$
$P_1 \quad L_1 \quad R_1$
$P_2 \quad L_2 \quad R_2 $
$\vdots$
$P_T \quad L_T \quad R_T$

  • 入力は全て整数である。
  • $1 \le T \le 10^5$
  • $|P_i,L_i,R_i| \le 2 \times 10^5$
  • $L_i \le R_i$

出力

出力は $T$ 行にわたります。$i(1 \le i \le T)$ 行目には $i$ 個目のテストケースの答えを出力してください。

サンプル

サンプル1
入力
1
13 69 70
出力
1

$f(x)=13$ の異なる整数解を $5$ 個以上持ち、かつ $f(x)=69$ の整数解を持つような整数係数多項式 $f(x)$ は、例えば $2 x^5 - 16 x^4 + 2 x^3 + 236 x^2 - 544 x + 333 $ があります。

また、$f(x)=13$ の異なる整数解を $5$ 個以上持ち、かつ $f(x)=70$ の整数解を持つような整数係数多項式 $f(x)$ は存在しないことが証明できます。

よってこのケースの解は $1$ です。

サンプル2
入力
4
8 17 28
-101 -164 -139
-217 -78 -8
9 -110 -59
出力
4
11
35
25

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