AOJ1109:Fermat's Last Theorem

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1109
問題文通り。与えられたzについて
z^3-max{x^3 + y^3| x>0, y>0, x^3 + y^3 <= z^3}(x,y,zは整数)
を計算する。

方針

xを決めて条件を満たす最大のyを二分探索で求めて計算する。
二分探索は割とすぐ思いつけたのでよい。

以下ソースコード

#include <iostream>

using namespace std;

int main(){
    int n;
    while(cin >> n && n){
        int cubic = n*n*n;
        int ret= 1 << 29;
        int ub = 1111,lb=1;
        int maxi = 1111;

        for(int i=1;i<=maxi;i++){
            ub = 1111;
            lb = 1;
            while(ub - lb > 1){
                int mid = (ub + lb) / 2;
                if(i*i*i + mid*mid*mid <= cubic){
                    lb = mid;
                }else{
                    ub = mid;
                }
            }
            maxi = lb;
            ret = min(ret, cubic - i*i*i - lb*lb*lb);
        }
        cout << ret << endl;
    }
}