c698: 整數溢位問題
Tags :
Accepted rate : 2人/2人 ( 100% ) [非即時]
評分方式:
Tolerant

最近更新 : 2019-04-14 18:37

Content

對於一個 $\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}$ 位元下相乘會發生溢位?

Input

首行有一正整數 $\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}$ 位元有號整數)。

Output

$\color{black}{p * q\ (l \le p,\ q \le r)}$ 溢位的數對總數

Sample Input
1
2 -2 1
Sample Output
3
測資資訊:
記憶體限制: 512 MB
公開 測資點#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
Hint :

範例測資中產生溢位的組合為 $\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}}$。

小心別溢位喔。

Tags:
出處:
[管理者:
icube (輸光光)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」