ConanKIDの小窝

ConanKIDの小窝

CF1514A 题解

posted on 2021-04-20 19:30:04 | under 题解 |

题目大意:给定长度为$n$的整数序列$a$,若能从中取出一些数,使得它们的积不为完全平方数,则输出YES,否则输出NO

结论:若序列$a$中存在非完全平方数,则输出YES;否则输出NO

证明:

先证必要性。若$a$中均为完全平方数,因为完平乘上完平仍为完平,所以此时任取一些数,那么他们的乘积必为完平。

再证充分性。若$a$中存在非完全平方数,则将这个数单独取出来,即可满足题目要求。

证毕。

代码就不放了。