- 「CEOI2018」玩具
为什么会WA?
- @ 2025-10-9 21:36:13
`#include<bits/stdc++.h> #define int long long using namespace std; const int N = 2e7 + 7; int a[N]; int n, ans; inline void dfs(int n, int x, int cnt){ if(x <= n) a[++ans] = cnt + n - 1; for(int i = x; i * i <= n; i++) if(n % i == 0) dfs(n / i, i, cnt + i - 1); } signed main(){ cin >> n; dfs(n, 2, 0); sort(a + 1, a + ans + 1); ans = unique(a + 1, a + ans + 1) - a - 1; cout << ans << "\n"; for(int i = 1; i <= ans; i++) cout << a[i] << " "; return 0; }``````` 为什么会WA 81 在[CEOI 2018]toy 提交是对的。
1 条评论
-
李宇桐 @ 2025-11-22 21:07:05
这段代码解决了一个数学问题:给定n天不同的玩具选择方式,求玩具总数m的所有可能值。
代码功能分析:
问题本质:将n分解为质因数的乘积形式,每种分解对应一个可能的玩具总数m 核心算法:使用DFS深度优先搜索遍历n的所有因数分解方式 数学原理:玩具选择方式数n = ∏(k_i),其中k_i是每种玩具的选择数量+1 输出结果:所有可能的玩具总数m = (∑k_i) - (因数个数) 代码特点:
使用DFS高效遍历所有因数分解组合 通过排序和去重确保结果唯一且有序 处理大数情况使用long long类型 优化搜索范围(i*i ≤ n)提高效率 这个程序能够正确计算出Johnny可能拥有的玩具总数,并输出所有可能的结果。
- 1
信息
- ID
- 16378
- 时间
- ms
- 内存
- MiB
- 难度
- 10
- 标签
- 递交数
- 3
- 已通过
- 0
- 上传者