题解 | 魔法棒

import java.util.Scanner;

/**
 * @author supermejane
 * @date 2025/10/3
 * @description 牛客算法学习篇-算法入门   BGN7魔法棒
 */
public class Main {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        while (n-- > 0) {
            Long a = sc.nextLong();
            System.out.println(isMagic(a) ? "Yes" : "No");
        }
    }
	
  	//使用递归，需要注意输入的数字为1 - 10^18, 需要使用Long
    public static boolean isMagic(Long a) {
        int half = (int)Math.sqrt(a);
        if ((long) half * half == a) return true;
        //只要有一个可行就可以， 注意i > 1不能为1
        for (int i = (int) Math.sqrt(a); i > 1; i--) {
            if (isMagic(a + 1 - (long) i * i)) return true;
        }
        return false;
    }
}
//题目的意思是n' = n - 1 + m * m有限轮迭代之后变成x, 可以看出迭代的顺序是无关的， 就是对于一个可行的序列1 -> 4 -> 12而言中间的结果的顺序是可以调换的。