视频加载失败

数论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 和 3
bool 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;
}

文章分享

如果这篇文章对你有帮助,欢迎分享给更多人!

数论1
https://www.xiaobaibai454.top/posts/study-26-11-09/
作者
Xiao_baibai
发布于
2026-11-09
许可协议
CC BY-NC-SA 4.0

评论区

Profile Image of the Author
Xiao_baibai
你是怎么找到这里的???
分类
最新动态
站点统计
文章
25
分类
4
标签
5
总字数
17,871
运行时长
0 天
最后活动
0 天前
站点信息
构建平台
GitHub Actions
博客版本
Firefly v6.16.8
文章许可
CC BY-NC-SA 4.0
文章目录