B2092 开关灯【入门】

浅浅的花香味﹌ 2023-09-25 17:19 65阅读 0赞

原题链接: [开关灯][Link 1]

# 开关灯 #

## 题目描述 ##

假设有  N N N 盏灯（ N N N 为不大于  5000 5000 5000 的正整数），从  1 1 1 到  N N N 按顺序依次编号，初始时全部处于开启状态；第一个人（ 1 1 1 号）将灯全部关闭，第二个人（ 2 2 2 号）将编号为  2 2 2 的倍数的灯打开，第三个人（ 3 3 3 号）将编号为  3 3 3 的倍数的灯做相反处理（即，将打开的灯关闭，将关闭的灯打开）。依照编号递增顺序，以后的人都和  3 3 3 号一样，将凡是自己编号倍数的灯做相反处理。问当第  N N N 个人操作完之后，有哪些灯是关闭着的？

## 输入格式 ##

输入为一行，一个整数  N N N，为灯的数量。

## 输出格式 ##

输出为一行，按顺序输出关着的灯的编号。编号与编号之间间隔一个空格。

## 样例 \#1 ##

### 样例输入 \#1 ###

### 样例输出 \#1 ###

1 4 9

## 样例 \#2 ##

### 样例输入 \#2 ###

### 样例输出 \#2 ###

1 4

思路：  
一开始所有灯都是亮的，如果要最后是关着的话，那么这个灯在整个过程中应该被开关奇数次，所以满足最后是关闭状态的灯，它的因子应该是奇数个，又因为完全平方数的因子是奇数个（这是一个定理，已经确定的），那么我们只需要找从1到n中有哪些数是完全平方数，那么最后这些灯就是关闭状态的。

为什么完全平方数的因子个数是奇数个

因为对于一个数x来说，存在因数m，必然存在另一个因数x/m，两个一对，而完全平方数的平方根对应的因数又是本身自己，所以一共有奇数个因子。

import java.util.Arrays;
    import java.util.Scanner;
    import java.util.*;
    
    public class Main {
        
        public static void main(String[] args) {
        
            Scanner in=new Scanner(System.in);
            int n=in.nextInt();
            for(int i=1;i<=n;++i){
        
                if(i*i<=n)
                    System.out.print(i*i+" ");
            }
        }
    }

[Link 1]: https://www.luogu.com.cn/problem/B2092