P1876 开灯[洛谷]

P1876 开灯[洛谷]

P1876 开灯[洛谷]

​​1.题目​​​​2.分析​​​​3.代码​​​​4.总结​​​​5.更新日志​​

1.题目

​​题目链接​​

题目描述

输入格式

输出格式

若干数，表示开着的电灯编号。

样例输入 #1

5

样例输出 #1

1 4

提示

【数据范围】

2.分析

exp:结论：只有完全平方数的约数个数为奇数[√n 与其它不成对]

证明：假设一个数为N，可拆分为 p1a1 * p2a2 * … * pkak 则其约数个数为 (a1+1)(a2+1)…*(ak+1) [不同约数选择时，ai+1种选择] 初始状态灯是关的，要使最终灯亮，则约数个数为奇数，则只能a1,a2,…ak均为偶数 则可找到一个数M = p1(a1/2) * p2(a1/2)… pk(ak/2) ， 使得 N = M^2 亦即N为完全平方数

3.代码

#include using namespace std;typedef long long LL;int main(){ LL n; scanf("%lld", &n); for (LL i = 1; i * i <= n; ++i) printf("%lld ", i*i); return 0;}

4.总结

约数

5.更新日志

2022.8.6 整理

欢迎交流、讨论、指正~ 不正确、不理解之处欢迎评论留言~

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。