Not Overflow Product

2 secs 1024 MB
Slephy's icon Slephy

普段はC++を使っているのにPythonを使ったあなた。

そういう日もありますね。

もし気が向いたら、多倍長整数型を使わずに解いてみてください。結構面倒ですよ。

多倍長整数を使わない解法

まずABA \leq B となるようにswapします。そのうえで4通りに場合分けを行いましょう。

以下、64ビット整数型の表せる最大値をMAX、最小値をMINと書きます。

A=0A=0 または B=0B=0

AB=0AB = 0なので、答えはYesです。

A>0A>0 かつ B>0B>0

式変形をすると AMAXBA \leq \lfloor \cfrac{MAX}{B} \rfloor を満たすならYes、そうでないならNoを出力すればよいとわかります。

A<0A<0 かつ B<0B<0

式変形をすると AMAXBA \geq \lfloor \cfrac{MAX}{B} \rfloor を満たすならYes、そうでないならNoを出力すればよいとわかります。

A<0A<0 かつ B>0B>0

式変形をすると AMINBA \geq \lceil \cfrac{MIN}{B} \rceil を満たすならYes、そうでないならNoを出力すればよいとわかります。