不会真有人用这个模拟吧,这个240的数据量O(n)都够呛
那怎么办呢?
我们仔细读题,发现每个灯按开关的次数都是它们所有的因子数
所以我们要找到拥有奇数个因子数的数
但我们发现,如果一个数x有因子y,那它就必然有因子(x/y)等等我好像说过这句话,那怎么可能嘛!
我们再看一下样例,
好像有什么规律……
我们用上面的代码把输入数调大点,如100
输出:
……等等,这些数都是完全平方数!!!
没错,完全任意平方数x因为有因子sqrt(x),而用x除以这个因子竟然还是sqrt(x)!
这样就减少了一个因子,因子数由偶数变成了奇数
所以我们只要输出n以内的完全平方数
时间复杂度:O(n)O(\sqrt{n})O(n )