【洛谷】P1876 开灯
2024-09-02 16:39:39
P1876 开灯
题目背景
该题的题目是不是感到很眼熟呢?
事实上,如果你懂的方法,该题的代码简直不能再短。
但是如果你不懂得呢?那。。。(自己去想)
题目描述
首先所有的灯都是关的(注意是关!),编号为1的人走过来,把是一的倍数的灯全部打开,编号为二的的把是二的倍数的灯全部关上,编号为3的人又把是三的倍数的灯开的关上,关的开起来……直到第N个人为止。
给定N,求N轮之后,还有哪几盏是开着的。
输入输出格式
输入格式:
一个数N
输出格式:
若干数,表示开着的电灯编号
输入输出样例
输入样例#1:
5
输出样例#1:
1 4
说明
1<=N<=2^40
数学题!
#include<cstdio>
#include<cmath>
long long n;
int main()
{
scanf("%lld",&n);
long long a=sqrt((double)n);
for(int i=1;i<=a;i++){
printf("%lld ",i*i);
}
}
从现在开始再也不水水题了
这将是水库里最后一道水题
想到之后很显然,操作k次灯是关着的,操作k+1次灯是开着的。被操作的次数取决于灯编号的因数个数,只有满足存在p使n=p^2,编号n才有奇数个公因数。
可以用反证法证明。
假设一个正整数n,使n满足n=p*p,p∈Z且p有偶数个因数。则另有一正整数q满足n=q*q,则n的算术平方根为p和q,而正整数的算术平方根只有一个,二者矛盾。
最新文章
- 初学mongodb笔记
- Android活动管理工具
- 【CF刷题】14-05-12
- HDU 2444 The Accomodation of Students(判断是否可图 + 二分图)
- Android 拨号器的实现 [视频1]
- Web Host消息处理管道
- JS内置对象-自定义对象
- MySQL数据库 Event 定时执行任务.
- Vue通过路由 query传递参数
- Kotlin中三元运算符
- Windows7的MySQL数据库的安装
- 配置SQL Server 2016无域AlwaysOn(转)
- webpack初识
- Tidb缩减tikv机器
- Java通过在主循环中判断Boolean来停止线程
- input type= file 如何更改自定义的样式
- Winform下的语言国际化,几行代码轻松实现
- linux tar 解压出错
- MP1593 RT8272 ACT4070 制作的DC-DC稳压电源
- C#框架及概念