積(掛け算した値)がオーバーフローするかチェックする

はじめに

ABC169のBで躓いたので。
冷静じゃなくなると間違いが見えなくなる。

結論

一度掛け算し、その積をかけた数の片方で割った場合同じ値になるかをみている。

#define ul unsigned long
bool IsOverflow(ul a, ul b){
    ul x = b * a;
    return (x/a != b);
}

補足

負の数が含まれると不正解パターンがある。
というかコンテスト中にlonglongを用いていて失敗した。

#define ll long long
bool IsOverflow(ll a, ll b){
    ll x = b * a;
    return (x/a != b);
}

これを使ってしまうと下のようになる。
割とトラウマ...。

コード

// こっちでも行ける
bool IsOver(ll a, ll b, ll lim){
    return (b > lim/a);
}

// 成功した関数
bool IsOverflow(ul a, ul b){
    ul x = b * a;
    return (x/a != b);
}

// コンテスト中の関数
bool IsOver_ng(ll a, ll b){
    ll x = b * a;
    if(x/a != b){
        return true;
    }else{
        return false;
    }
}


void Main(){
    ul limit = pow(10,18);
    ul n;
    cin >> n;
    vector<ul> a(n);
    for(ul i = 0; i<n;i++){
        cin >> a[i];
        if(a[i] == 0){
            ct(0);
            return;
        }
    }
    ul ans = 1;
    for(ul i = 0; i < n; i++){
        //if(IsOver(ans,a[i], limit)){
        if(IsOverflow(ans,a[i])){
            ct(-1);
            return;
        }else {
            ans *= a[i];
            if ( ans > limit ){
                ct(-1);
                return;
            }
        }
    }
    ct(ans);
    return;
}

int main() {
    Main();
}