luogu#P9913. 「RiOI-03」water problem

    ID: 13880 远端评测题 1000ms 128MiB 尝试: 1 已通过: 1 难度: 3 上传者: 标签>数学洛谷原创O2优化洛谷月赛Ad-hoc

「RiOI-03」water problem

题目描述

给定一个正整数 nn,问一个正方形能否被分割为 nn 个小正方形(不要求大小相等),输出 YesNo。多组数据。

分割的不严格定义可以理解为切一刀。但是切出的这一刀必须是线段,且其端点必须在正方形的边界上或先前切出的线段上。

输入格式

第一行一个正整数 TT

对于每组数据,一行一个正整数 nn

输出格式

对于每组数据,分别一行一个字符串,YesNo 表示方案的存在与否。

3
4
3
256
Yes
No
Yes

提示

样例解释 1

显然,正方形无法分割为 33 个小正方形;
由于 4=224 = 2^2256=162256 = 16^2,则它们均能被分割成若干个全等的小正方形。

数据规模与约定

  • Subtask 0(10 pts):nn 是偶数。
  • Subtask 1(35 pts):n8n \leq 8
  • Subtask 2(55 pts):无特殊限制。

对于所有数据,1T1051 \leq T \leq 10^51n1091 \leq n \leq 10^9