CF1514A Perfectly Imperfect Array 题解
2024-09-01 04:59:01
Content
给定一个长度为 \(n\) 的序列,问是否存在一个非空子序列,使得这个子序列所有元素的积不是完全平方数。
数据范围:\(t\) 组数据,\(1\leqslant t\leqslant 100\),\(1\leqslant n\leqslant 100\),序列中的元素在 \(1\) 到 \(10^4\) 之间。
Solution
我们不难想到,如果这个序列中所有的元素都是完全平方数,那么肯定不存在积不是完全平方数的子序列,因为无论怎么取,积一定是完全平方数。
我们不妨稍微证明一下:设这个序列可以表示成 \(p_1^2,p_2^2,\dots,p_n^2\),然后假设存在积不是完全平方数的子序列,并且你取的元素的下标为 \(i_1,i_2\dots,i_k\),那么他们的积就是 \(\prod\limits_{j=1}^ka_{i_j}=\prod\limits_{j=1}^kp_{i_j}^2=(\prod\limits_{i=1}^kp_{i_j})^2\),显然这是一个完全平方数,与假设矛盾,故不存在积不是完全平方数的子序列。证毕。
我们再看,如果假设存在非完全平方数的元素,由于单个元素也能组成子序列,因此我们只需要取那个非完全平方数的元素,就可以满足题目要求。
那么这道题就写完了。
Code
int main() {
MT {
int n = Rint, fl = 0; while(n--) {
int x = Rint;
if((int)sqrt(x) * (int)sqrt(x) != x) fl = 1;
}
fl ? YES : NO;
}
return 0;
}
最新文章
- Thinkphp源码分析系列(二)–引导类
- Java-小数点控制
- 使用ProxychainsMac下安装及配置
- python_way day12 RabbitMQ ,pymysql
- Leetcode#128 Longest Consecutive Sequence
- npm安装插件提示
- 第二百八十七天 how can I 坚持
- 利用C++ RAII技术自动回收堆内存
- jvm之内存分配与回收策略
- 快速入门cocos2d-x jsbinding
- redux middleware 源码分析
- Swift3中方法可变参数语法的一些改变
- SGD、GD
- (栈)leetcode496. Next Greater Element I
- laravel5.8笔记十:Redis操作
- Python基础02_基本数据类型_以及while
- (后端)shiro:Wildcard string cannot be null or empty. Make sure permission strings are properly formatted.
- 安装Visual Studio开发平台
- LeetCode--326--3的幂
- 一、Blender/Python 快速入门
热门文章
- 多声部处理细节之crossstaff音符处理
- Codeforces 1442D - Sum(找性质+分治+背包)
- open 函数小结
- 从零构建Java项目(Maven+SpringBoot+Git) #02 奥斯丁项目
- 技术管理进阶——Leader的模型、手段及思维
- c++ cmake及包管理工具conan简单入门
- Sharding-JDBC 简介
- Identity Server 4 从入门到落地(八)—— .Net Framework 客户端
- 转 序列化Serializable和Parcelable的区别详解
- 【Linux】【Basis】【网络】网络相关的内核参数