P9913 题解

Jasonshan10 · 2023-12-12 09:09:52 · 题解

题意

• 给定一个正整数 n，问一个正方形能否被分割为 n 个小正方形（不要求大小相等）。

思路

• 分析：由正方形的分割图，我们发现任何一个正方形都可在原来的基础上增加 3k 个正方形，所以可以将自然数分为 3 类，3k，3k+1，3k+2 分别进行考虑能够做到。

• 当 n=4，n=6，n=8时分别有符合要求的解。

• 因为 n=4 有解，所以任何 4+3k(k\ge 0) 的都有解。

• 因为 n=6 有解，所以任何 6+3k(k\ge 0) 的都有解。

• 因为 n=8 有解，所以任何 8+3k(k\ge 0) 的都有解。

• 很明显，在 n=1 的情况下也是有解的。

• 综上所述，只有当 n=2，n=3，n=5 时，无解。

• 所以当 n=2，n=3，n=5 时，输出 NO，否则输出 YES。

代码

#include <bits/stdc++.h>
using namespace std;
int main(){
    int T;
    scanf("%d",&T);
    while (T--){
        int n;
        scanf("%d",&n);
        if (n==2||n==3||n==5){
            printf("No\n");
        }
        else{
            printf("Yes\n");
        }
    }
    return 0;
}