【题解】Luogu P1876【开灯】

背景

这是水题,但也有定理。

分析

首先模拟一下:

很直观的就可以看到完全平方数会在n次操作后变为亮着的状态。

引理:只有完全平方数的因数个数为奇数。
证明:
由算术基本定理:$N=\prod_{i=1}^{k}p_{i}^{a_{i}}$,$p_{i}$为质数。
由约数个数定理:$GG=\prod_{i=1}^{k}(a_{i}+1)$
因为$N$为完全平方数,易知$a_{i}$为偶数,那么$a_{i}+1$为奇数,显然奇数$\times$奇数$=$奇数,则完全平方数的约数个数为奇数个。
证毕。
于是这就是水题了。

代码

#include<cstdio>
typedef long long int64;

int main(){
    printf("1 ");
    int64 n;scanf("%lld",&n);

    for(int i = 2;i <= n;i++){
        if(i * i <= n) printf("%lld ",i * i);
        else break;
    }

    return 0;
}