【洛谷】【数论】P1876 开灯

【题目描述:】

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

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

【输入格式:】

一个数N,表示灯的个数和操作的轮数

【输出格式:】

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

【说明:】

$ 1\ <=\ N\ <=\ 2^40 $

[算法分析:]

一看n的范围就懵了,一开始想的是开一个数组模拟,\(2^40\)的一维数组是绝对是开不下的。

仔细观察,发现灯的个数,人的个数都是n

如果编号为i的一盏灯最后的状态是关,那i的因子个数一定有偶数个(开和关的操作成对出现)

找开着的灯就变成了找有奇数个因子的数。

设一个数\(n\),\(n∈N^*\)

现有一个数\(i\),\(i∈N^*\) 且 \(i<=n\)

若\(i|n\),则\((n/i)|n\)

当\(i ≠ n/i\)时,就得到了两个\(n\)的因数

若\(i = n/i\),则这个数为完全平方数,所以枚举小于\(n\)的完全平方数就好。

[Code:]

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std; long long n; int main() {
scanf("%lld", &n);
long long l = sqrt(n);
for(int i=1; i<=l; ++i)
printf("%lld ", 1LL*i*i);
}
上一篇:Spring-AOP用法总结


下一篇:docker构建镜像