题解 | 魔法棒

#include <stdio.h>
int main() {
   //魔法棒分裂的本质：把一根魔法棒变为k^2根，从而增加k^2-1根魔法棒，即每次从集合{3，8，15，24……}中选择增量；
   //问题就变成了：能否找到a,b,c……使得x-1=3a+8b+15c……
   //而由著名的硬币定理知道，由于gcd(3,8)=1,不能被3和8线性组成的最大数是3*8-3-8=13，即从14开始，每个数都能表示成3*a+8*b，即只要x>=15，一定可以由1分裂得到。
   //对于x<15的情况，可枚举出答案，不可以的有2，3，5，6，8，11,14。
   int t;
   scanf("%d",&t);
   long long x;
   while(t--){
    scanf("%lld",&x);
    if(x>=15||x==1||x==4||x==7||x==9||x==10||x==12||x==13)
    printf("Yes\n");
    else
     printf("No\n");
   }
   return 0;
}