對於一個 $\color{black}{m}$ 位元的有號整數，其能儲存的數字範圍為 $\color{black}{[-2^{m-1},\ 2^{m-1})}$ ，當運算過程超出這個範圍，就會產生溢位，這時記憶體儲存的數值可能無法預期。
下圖兩軸 $\color{black}{x,\ y}$ 為 8 位元有號整數，以黑色繪製出相乘發生溢位的位置。
現在問題來了，在給定的範圍 $\color{black}{[l,\ r]}$ 中，有多少數對 $\color{black}{(p, q)}$ 滿足 $\color{black}{p,\ q}$ 在 $\color{black}{m}$ 位元下相乘會發生溢位？
首行有一正整數 $\color{black}{T \le 100}$ 代表測資筆數。
接下來 $\color{black}{T}$ 行，每行有三個整數 $\color{black}{m, l, r}$ 以空格隔開，其中 $\color{black}{2 \le m \le 32\text{ 且}-2^{m - 1} \le l \le r < 2^{m - 1}}$ (意即 $\color{black}{l, r}$ 為合法的 $\color{black}{m}$ 位元有號整數)。
$\color{black}{p * q\ (l \le p,\ q \le r)}$ 溢位的數對總數
1 2 -2 1
3
公開 測資點#0 (10%): 1.0s , <1M
公開 測資點#1 (10%): 1.0s , <1M
公開 測資點#2 (10%): 1.0s , <1M
公開 測資點#3 (10%): 1.0s , <1M
公開 測資點#4 (10%): 1.0s , <1M
公開 測資點#5 (10%): 1.0s , <1M
公開 測資點#6 (10%): 1.0s , <1M
公開 測資點#7 (10%): 1.0s , <1M
公開 測資點#8 (10%): 1.0s , <1M
公開 測資點#9 (10%): 1.0s , <1M
範例測資中產生溢位的組合為 $\color{black}{(-2, -2), (-2, -1), (-1, -2)}$。
對於 $\color{black}{\text{1%~10%}}$ 測資， $\color{black}{r - l \le 10^3}$。
對於 $\color{black}{\text{11%~30%}}$ 測資， $\color{black}{r - l \le 10^6}$。
對於 $\color{black}{\text{31%~60%}}$ 測資， $\color{black}{l \ge 0}$。
對於所有測資， $\color{black}{2 \le m \le 32\text{ 且}-2^{m - 1} \le l \le r < 2^{m - 1}}$。
小心別溢位喔。
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
|
沒有發現任何「解題報告」
|
|||||