luogu P1876 开灯

最新推荐文章于 2024-07-11 11:49:28 发布

_ivnoniecre_

最新推荐文章于 2024-07-11 11:49:28 发布

阅读量365

点赞数

分类专栏： OI颓废史

本文链接：https://blog.csdn.net/manbell_shaw/article/details/78376552

版权

OI颓废史专栏收录该内容

16 篇文章

订阅专栏

本文探讨了一道有趣的问题：初始状态下关闭的所有灯，在不同编号的人依次改变特定编号灯的状态后，哪些灯会保持开启状态。文章揭示了灯是否开启与该灯编号是否为完全平方数之间的联系。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

首先所有的灯都是关的（注意是关！），编号为1的人走过来，把是一的倍数的灯全部打开，编号为二的的把是二的倍数的灯全部关上，编号为3的人又把是三的倍数的灯开的关上，关的开起来……直到第N个人为止。

给定N，求N轮之后，还有哪几盏是开着的。

一道像我一样辣鸡的辣鸡题，所以说我被同水平的辣鸡题卡思路了（想到了筛法，然后思路就RE了）。

显然能对于每一盏灯，只有它的编号的因子的人会对它进行操作，并且如果操作是偶数次，就会灭，否则就会亮。

然后我们来考虑什么时候一个数的因子有奇数个。

对于一个数，进行因数分解（注意不是质因数），比如说6，一个因子是3，另一个因子就是6/3=2，所以说因子是成对的，那什么时候才会有奇数个因子呢？

当n/m=m时，有一对因子重合了，变成了一个，然后就VERY GOOD 了，很明显，完全平方数有奇数个因子。

然后就OK了。

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<string>
#include<cmath>
#define ll long long
using namespace std;
ll n;
int main()
{
	scanf("%lld",&n);
	for(ll i=1;i<=n;i++)
	{
		if(i*i>n)break; 
		else printf("%lld ",i*i);
	}
	return 0;
}