【洛谷】P1876 开灯

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,而正整数的算术平方根只有一个,二者矛盾。

上一篇:洛谷P1876开灯 题解


下一篇:洛谷 P1876 开灯