数论1
406 字
2 分钟
数论1
题目描述
有 n 盏灯,编号为 1 到 n,初始全部关闭。 依次考虑 i = 1, 2, …, n,若 i 不含 2, 3 以外的质因数,则将所有编号为 i 的倍数的灯切换一次状态:关闭的灯打开,打开的灯关闭。 请问所有操作结束后,有多少盏灯处于打开状态?
【名词解释】 质因数:也称质因子。对于正整数 x,如果存在质数 p 使得 x 能被 p 整除,则称 p 是 x 的质因子。例如,12 的质因子有 2, 3。
输入描述
输入一个整数 n (1 <= n <= 2 * 10^5),表示灯的数量。
输出描述
输出一个整数,表示所有操作结束后处于打开状态的灯的数量。
示例1
输入
1输出
1示例2
输入
6输出
3我的代码
#include <iostream>#include <vector>
using namespace std;
// 判断一个数是否只含有质因数 2 和 3bool isValid(int x) { while (x % 2 == 0) { x /= 2; } while (x % 3 == 0) { x /= 3; } return x == 1;}
int main() { int n; cin >> n;
// is_open[i] 表示第 i 盏灯是否打开 vector<bool> is_open(n + 1, false);
// 依次考虑 i = 1, 2, ..., n for (int i = 1; i <= n; ++i) { if (isValid(i)) { // 如果 i 符合条件,则切换其所有倍数灯的状态 for (int j = i; j <= n; j += i) { is_open[j] = !is_open[j]; // 状态反转 } } }
// 统计处于打开状态的灯的数量 int count = 0; for (int i = 1; i <= n; ++i) { if (is_open[i]) { count++; } }
cout << count << endl;
return 0;}文章分享
如果这篇文章对你有帮助,欢迎分享给更多人!




