AcWing 1221. 四平方和

Problem: AcWing 1221. 四平方和

思路

这是一个四平方和的问题，我们需要找到四个整数a、b、c和d，使得a^2 + b^2 + c^2 + d^2 = n。我们可以通过三层循环来枚举a、b和c的值，然后计算d的值。如果a^2 + b^2 + c^2 + d^2 = n，那么我们就找到了一个解。

解题方法

我们首先枚举a的值，从0开始，直到a^2 * 4 > n。然后对于每一个a的值，我们枚举b的值，从a开始，直到a^2 + b^2 * 3 > n。然后对于每一个b的值，我们枚举c的值，从b开始，直到a^2 + b^2 + c^2 * 2 > n。然后我们计算d的值，d = sqrt(n - a^2 - b^2 - c^2)。如果a2 + b^2 + c^2 + d^2 = n，那么我们就找到了一个解，打印出a、b、c和d的值，并结束程序。

复杂度

时间复杂度:

我们需要枚举a、b和c的值，所以时间复杂度为$O(n^{(}3/2))$。

空间复杂度:

我们只需要常数的空间来存储a、b、c和d的值，所以空间复杂度为$O(1)$。

Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;

public class Main {
	static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
	static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
	static StreamTokenizer sr = new StreamTokenizer(in);
	static int n;

	public static void main(String[] args) throws IOException {
		n = nextInt();
		for (int a = 0; a * a * 4 <= n; a++) {
			for (int b = a; a * a + b * b * 3  <= n; b++) {
				for (int c = b; a * a + b * b + c * c * 2 <= n; c++) {
					int d = (int) Math.sqrt(n - a * a - b * b - c * c);
					if (a * a + b * b + c * c + d * d == n) {
						out.println(a + " " + b + " " + c + " " + d);
						out.flush();
						return;
					}
				}
			}
		}

	}

	static int nextInt() throws IOException {
		sr.nextToken();
		return (int) sr.nval;
	}

}