1. 题目背景与需求分析
这道题目来自AHOI2018初中组竞赛,编号P4446,属于数学与编程结合的典型题型。题目要求我们对给定的正整数x进行"根式化简",即找到最大的正整数a和正整数b,使得x=a³×b,且b不能再被任何整数的立方整除(即b不包含立方因子)。
举个例子,当x=200时:
- 200可以分解为2³×25(此时a=2,b=25)
- 也可以表示为1³×200(a=1,b=200)
但第一种分解方式中a更大,因此正确答案是a=2。
1.1 数学基础解析
要解决这个问题,我们需要理解几个关键数学概念:
- 立方数:一个整数的三次方(如1=1³,8=2³,27=3³等)
- 立方因子:一个数能被某个整数的立方整除,这个立方数就是它的立方因子
- 无立方因子数:不能被任何大于1的整数的立方整除的数
题目本质上是要求我们将x分解为最大可能的立方数部分(a³)和剩余的无立方因子部分(b)。
需要模型API调用? 免费领10W Token,多模型网关一键接入 Claude、DeepSeek 等主流模型。
2. 算法设计与思路
2.1 暴力解法分析
最直观的想法是尝试所有可能的a值,从大到小检查x是否能被a³整除:
cpp复制int max_a = 1;
for(int a = cbrt(x); a >= 1; a--) {
if(x % (a*a*a) == 0) {
max_a = a;
break;
}
}
int b = x / (max_a*max_a*max_a);
这种方法虽然简单,但当x很大时(题目中x可达1e18),效率会非常低。例如对于x=1e18,我们需要检查1e6次,这在竞赛中会超时。
2.2 优化思路:质因数分解
更高效的解法是基于质因数分解:
- 对x进行质因数分解,得到x = p₁^e₁ × p₂^e₂ × ... × pₖ^eₖ
- 对于每个质因数pᵢ,其指数eᵢ可以表示为eᵢ = 3×qᵢ + rᵢ(其中0 ≤ rᵢ < 3)
- 则a = ∏pᵢ^{qᵢ},b = ∏pᵢ^
例如x=200=2³×5²:
- 对于2:e₁=3=3×1+0 → q₁=1, r₁=0
- 对于5:e₂=2=3×0+2 → q₂=0, r₂=2
- 因此a=2¹×5⁰=2,b=2⁰×5²=25
