Problem SQUFOF - Dane wychodzą poza long long

Question

Witam,

Napisałem cały kod do zadania : https://szkopul.edu.pl/problemset/problem/fof/site/?key=statement.
Natomiast w kodzie zielonym może dojść do większych liczb niż pomieści long long, z uwagi na to że n może być nawet 10^18 a m aż 5. Ma może ktoś pojęcie jak temu zapobiec? Niestety moja metoda nie działa.

#include <iostream>

using namespace std;

bool oblicz(long long mid, long long m,long long n){
    long long ob = 1;
    for(int i=0;i<m;++i)
    {    
        if(ob * mid > n)
            return true;
        ob *= mid;
    }
    if(ob > n)
        return true;
    else
        return false;
}

long long bs(long long n,long long m){
    long long l=-1,r=n;
    long long mid;
    while(r - l > 1){
        mid = (l + r) / 2;
        if(oblicz(mid,m,n))
            r = mid;
        else
            l = mid;
    }
    return l;
}

int main(){
    int T;
    cin >> T;

    for(int i=0;i<T;++i){
        long long n,m;
        cin >> n >> m;
        if(m == 1)
            cout << n << '\n';
        else if(n == 1)
            cout << 1 << '\n';
        else{
            long long a = bs(n,m);
            cout << a << '\n';
        }
    }
    return 0;
}

 

Comments

Ale to m to stopień pierwiastka - więc liczby nie powinny przekraczać 64 bitów.

10 bitów to 3 cyfry dziesiętne - 10^18 (18 cyfr) powinno wystarczyć 60 bitów.

---

Gdy mid w podkreślonej sekcji wyniesie 10^18 i pomnożymy go dajmy na to 5 razy przez siebie to wyjdzie daleko

---

@Dani, Jeżeli założymy że będą to liczby tylko dodatnie, to możesz spróbować z "unsigned ".