洛谷P1876 开灯
题目背景
该题的题目是不是感到很眼熟呢?
事实上，如果你懂的方法，该题的代码简直不能再短。
但是如果你不懂得呢？那。。。（自己去想）
题目描述
首先所有的灯都是关的（注意是关！），编号为1的人走过来，把是一的倍数的灯全部打开，编号为二的的把是二的倍数的灯全部关上，编号为3的人又把是三的倍数的灯开的关上，关的开起来……直到第N个人为止。
给定N，求N轮之后，还有哪几盏是开着的。
输入输出格式
输入格式：
一个数N，表示灯的个数和操作的轮数
输出格式：
若干数，表示开着的电灯编号
输入输出样例
输入样例#1：
5输出样例#1：
1 4说明
1<=N<=2^40
数学题！
一道代码难度入门的提高难度题
我们考虑一下，编号为 i的灯只会被它的约数所操作
而它最后是开着的，所以说一定被操作了奇数次
只有一个数是完全平方式的约数才是奇数
所以只要输出i to n中的完全平方数就好了
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define LL long long
using namespace std;
const int MAXN=1e7+10;
inline int read()
{
char c=getchar();int flag=1,x=0;
while(c<'0'||c>'9') {if(c=='-') flag=-1;c=getchar();}
while(c>='0'&&c<='9') x=x*10+c-48,c=getchar();return x*flag;
}
LL n;
LL a[MAXN];
int main()
{
LL n=read();
for(int i=1;i<=sqrt(n);i++)
printf("%lld ",(LL)i*i);
return 0;
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017-11-08 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录