C++で計算結果が10の18乗を超えた時という条件を実装したい

Question

#前提・実現したいこと
競技プログラミング初心者です。
Pythonからプログラミングを始め、C++を今回始めて触っています。

AtCoderのB - Multiplication2 を解こうとしています。
値の大きさより、intではなくlong longを使ったコードを作成しました。
しかし、long longでも10の19乗を超える値は、オーバーフローしてしまいます。

#試したこと
こちらのサイトに書かれてい解決策を参考に、値に解決しようとしました。
しかし、2つ目のifに書かれている-1が出力されてしまいます。

#発生している問題・エラーメッセージ
計算結果がオーバーフローしてしまって、値がうまく出力されない。

#該当のコード

#include <iostream>
using namespace std;
int main(void){
    // Your code here!
    int N; cin>>N;
    int ans=1;
    for (int i=0;i<N;i++){
        int num; cin>>num;
        if (num==0) {
            cout<<"0"<<endl;
            exit(0);
        }

        if (ans<=1e18/num){
            cout<<"-1"<<endl;
            exit(0);
        }

        ans*=num;
    }
    cout<<ans<<endl;
}

#教えていただきたいこと
２点あります。

1、どのようにコードを変えればいのか？
3、解決方法の導き方

自力で解決できるようになりたいので！

Comments

[kazuma-s]

> 値の大きさより、intではなくlong longを使ったコードを作成しました。

質問のコードには long long が使われていません。
作成したコードに変更してください。

Answer 1

以下を直せば動きました。

• ansとnumはlong longにする。(intだと2^31-1が上限なので、計算中にオーバフローしている)
• if(ans > 1e18/num)に直す。（他の方の丁寧な回答を参照してください）
• 1e18を1000000000000000000に直す。

　これは自分の予想が含まれるのですが1e18はdouble型になるため、1e18/numもdouble型になっている。double型の有効桁数が10進数で15桁程度なので、1e18/999999000001の計算結果が1000000.999999999998999999ではなく1000001.00000に丸められてしまう。その結果-1のルートに入らない。）

Comments

[YUMA-NAGAO]

教えていただきありがとうございます！

Answer 2

__int64型だと値の範囲は-9223372036854775808~9223372036854775807
です。
これだとオーバーフローしないと思いますが。

Answer 3

問題文を見るに，結果が10^18を超える場合は-1を出力せよ，とのこと．
素直に考えれば，
if( 計算中の値 >= 1e18 ){ -1を出力 }
という形になるのでは？

ansにnumを乗じたら10^18以上になるかどうかをチェックするならば，
その条件式とはans * num >= 1e18という形でしょう．
これを単純に書いたならば，
if( ans >= 1e18/num ){ -1を出力 }
となるのではないでしょうか．

Comments

[YUMA-NAGAO]

if( ans >= 1e18/num ){ -1を出力 }
をすると、long longで定義できる範囲の価を超えてしまうので、それ以外の方法で、やろうとしています…。
c++で、10の18乗などの大きな値を保持できる型などがありましたら、教えていただきたいです

[ozwk]

「超える」なので ans>1e18/num ですね。

[fana]

とりあえず理屈の上で，

> if (ans<=1e18/num)

では　不等号の向きが違うのではないか？　ということを述べたつもり．

> 2つ目のifに書かれている-1が出力されてしまいます。

という事柄の原因として．

[Zuishin]

大きい数で考えると難しいですね。9 を超えたら -1 というルールで考えてみましょう。
5 に 2 をかけると 9 を超えるかどうかは、5 > 9 / 2 が true になることで調べられます。5 > 4.5 なので 5 × 2 は 9 を超えます。

ただし 4.5 という小数が使えない場合はもう一工夫必要です。
9 + 1 を 2 で割ってみましょう。かけられる数がそれ以上であれば 10 以上になる、つまり 9 を超えることになります。5 >= (9 + 1) / 2 なので、5 に 2 をかけると 10 以上になることがわかります。

unsigned long long なら 10 の 19 乗を保持できるので同じように計算できるのではないでしょうか。

[YUMA-NAGAO]

みなさま、教えていただきありがとうございました！！！！！！
ans >1e18/numにしても、-1が帰ってこないです…。
https://paiza.io/projects/NL08H4zBoLgZPbQ18MnSkg

[Zuishin]

でしょうね。