洛谷 P1876 开灯

传送门

洛谷 P1876 开灯

洛谷 P1876 开灯

这道题凭什么是洛谷 P1876 开灯

就因为它代码短?!

还是我太菜了...

第$i$盏灯的开关与否只由其约数个数决定,又有约数公式:

当$n=p_1^{a_1}p_2^{a_2}...p_n^{a_n}$时,
约数个数$=(a_1+1)(a_2+1)...(a_n+1)$
要使灯亮着,则$(a_1+1)(a_2+1)...(a_n+1)$是奇数。
于是$a_1, a_2, a_3, ... a_n$都是偶数。
所以$n=m^2, m=p_1^{a_1/2}p_2^{a_2/2}...p_n^{a_n/2}$
于是所有的完全平方数都满足条件。

Code:

#include<bits/stdc++.h>
#define RG register
using namespace std;
long long n;
int main()
{
scanf("%lld", &n);
for(RG long long i=;i<=(long long)sqrt(n);i++) printf("%lld ", i*i);
return ;
}
上一篇:【洛谷】P1876 开灯


下一篇:洛谷 P1876 开灯(思维,枚举,规律题)