AOJ1109 Fermat's Last Theorem

AOJ Volume11

問題リンク Fermat's Last Theorem

  • 概要

整数zが与えられる。z^3を超えないx^3+y^3を見つけ、z^3-(x^3+y^3)を計算せよ。xとyは0より大きい整数とする。
1 < z < 1111

  • 解法

iを1, jをzとします。
i^3+j^3がzを超えたならjを1つ減らし、そうでないならばiを1つ増やします。これをi<=jである間続けます。

  • ソース
import java.util.Scanner;

//Fermat's Last Theorem
public class AOJ1109 {

	void run(){
		long[] p = new long[1111];
		for(int i=0;i<1111;i++)p[i]=(long) Math.pow(i, 3);
		Scanner sc = new Scanner(System.in);
		while(true){
			int z = sc.nextInt();
			if(z==0)break;
			int i=1, j=z;
			long max = 0;
			while(i<=j){
				long val = p[i]+p[j];
				if(val<=p[z]){
					i++;
					max = Math.max(max, val);
				}
				else j--;
			}
			System.out.println(p[z]-max);
		}
	}
	
	public static void main(String[] args) {
		new AOJ1109().run();
	}
}