ARTICLE · 1377739
GESP 2024年12月 真题 奇妙数字 完整题解(数论)
小杨认为⼀个数字 x 是奇妙数字当且仅当 x=pᵃ, 其中 p 为任意质数且 a 为正整数。 例如,8=x³ , 所以 8 是奇妙数字, 而 6 不是。
对于⼀个正整数 , 小杨想要构建⼀个包含 m 个奇妙数字的集合 x₁,x₂,…,xₘ, 使其满足以下条件:
· 集合中不包含相同的数字。
· x₁× x₂× … × xₘ 是 n 的因子(即 x₁,x₂,…,xₘ 这 m 个数字的乘积是 n 的因子) 。
小杨希望集合包含的奇妙数字尽可能多, 请你帮他计算出满⾜条件的集合最多包含多少个奇妙数字。
这题光看代码容易绕进去,先找个生活里的比方,比方对了,代码就是照着抄。
今天刷 GESP 2024年12月 的这道数论题。先说结论:思路只有一句话,难的是把这句话不折不扣地落成代码。
题目:奇妙数字
场次:2024年12月 五级|难度:五级
知识点:数学 数论
链接:https://www.acgo.cn/problemset/info/75445
小杨认为⼀个数字 x 是奇妙数字当且仅当 x=pᵃ, 其中 p 为任意质数且 a 为正整数。 例如,8=x³ , 所以 8 是奇妙数字, 而 6 不是。 对于⼀个正整数 , 小杨想要构建⼀个包含 m 个奇妙数字的集合 x₁,x₂,…,xₘ, 使其满足以下条件: · 集合中不包含相同的数字。 · x₁× x₂× … × xₘ 是 n 的因子(即 x₁,x₂,…,xₘ 这 m 个数字的乘积是 n 的因子) 。 小杨希望集合包含的奇妙数字尽可能多, 请你帮他计算出满⾜条件的集合最多包含多少个奇妙数字。
一句话概括:用数学 数论把题目要求原样翻译成代码,属于考场上必须拿满分的题。
前提一,容器够不够大。题干没直接写范围,但参考代码里用了 long long,说明中间结果会超过 21 亿——照抄类型就不会错。
前提二,两头有没有照顾到。数据从 1 开始编号,读入和循环都从 1 起,a[0] 留空不用,能省掉大量 ±1 的换算。
前提三,交出去的样子对不对。第三件,最后注意输出格式。题目要几行就几行,行内空格几个就是几个,行末的换行别丢——算法对了格式错了,一样判错,这分丢得最冤。
先说这个比方。这题像照着说明书装家具:零件(输入)就那几样,说明书(题面)一步一步写清楚了,别自己加步骤。
构造一个元素互不相同的集合,每个元素都是 pᵃ 形式(质数幂),且所有元素乘积是 n 的因子,要求集合元素尽可能多。把 n 质因数分解成 ∏ pᵢ^{eᵢ}。每个巧妙数字必须整体占用某个质数 p 的若干次幂,不能跨质数、也不能重复质数。对每个质数 pᵢ,我们想用它的幂 p¹, p², ..., pᵃ 尽量多,总指数 1+2+...+a ≤ eᵢ,取满足的最大 a,可提供的巧妙数字个数为 a。把所有质数的 a 相加即为答案。
比方和代码是一一对应的:比方里先说清「有几样东西」,对应代码里的变量;比方里「一个一个过」,对应那个循环。
建议先自己写二十分钟,卡住了再看。对着抄一遍的效果,比不上自己错一遍。
using namespace std;
#define ll long long
const int N = 1e5+10;
ll calc(ll x){
int ans = 0; // 初始化
ll tmp=1;
while(x>=tmp){
ans++;
x-=tmp;
tmp++;
}
return ans;
}
int main(){
ll n;
cin>>n; // 读入
ll ans = 0;
for(ll i=2;i*i<=n;i++){ // 遍历
if(n%i==0){ // 判断
int cnt = 0; // 初始化
while(n%i==0){
cnt++;
n/=i;
}
ans+=calc(cnt);
}
}
if(n!=1){ // 判断
ans+=calc(1);
}
cout<<ans<<"\n"; // 输出
}
代码在上面,这里只挑最关键的两段讲,其他都是顺手写的。
第一段,把数据读进来。
ll ans = 0;
读入这段只要盯一件事:变量类型装不装得下。其他都可以照抄。
第二段,核心处理。
if(n%i==0){
int cnt = 0;
while(n%i==0){
cnt++;
n/=i;
}
ans+=calc(cnt);
}
// …(这段后面还有,见上面的完整代码)
这段是整道题唯一需要想的地方,也是数论的落点。看循环时只问三句:从哪开始、到哪结束、每次加几。三句都对,这段就没错。
代码写完不算完,得验。验也有顺序,从样例开始。
样例输入
样例输出
按这个顺序走一遍,跟上面那个比方对上:
- 拿样例对一遍,输出和题目给的一模一样。
- 把数据压到最少,边界情形下答案仍然对。
- 看最后一行,结尾有换行,不多输出空行。
按危险程度从高到低排,第一条最常见:
- 累加结果溢出——写成
int sum = 0;就错,应该是long long声明累加变量。 - 下标起点错位——写成
for (i = 0; i < n; i++)存a[i]就错,应该是for (i = 1; i <= n; i++)存a[i]。 - 输出格式不符——写成
cout << ans;就错,应该是cout << ans << "\n";。 - 多组数据没清空——写成 全局数组直接用 就错,应该是 每组数据前
memset或重新赋值。
这题的经验压缩成三行,考前扫一眼就够。
- 这题考的:数学 数论——把题目条件一句一句翻译成代码,不添不减。
- 要记住的:取模题里乘法最容易溢出,乘之前先把两个因子都转成
long long。 - 下一步:拿同场次另一道题练手,换题型不换节奏,手感就稳了。
这题就讲到这。同一场次的题我会接着更,跟着刷完一整场,你对这个级别的题感就出来了。
- 本文属于《GESP 真题题解》系列,第 50 篇,真题按年份持续补齐,每篇都带完整可编译代码,题号可在 ACGO 直接提交验证。
- 还没动笔的话,先自己写一遍再回来看踩坑总结,比直接照抄代码收获大。
- 想跟完整系列的朋友点个关注,更新会第一时间推送。
- 本系列合集目录(按年份/组别排序)
GESP 的坑多半在边界和读题上。这道数论题把该注意的点都列在上面的表里了,提交前逐条过一遍。
今天想问你:这题的坑你踩了几个?踩得最多的那个,评论区报个数,我看看大家集中在哪。
把这篇转给一起刷题的同学,两个人对着讲一遍思路,比一个人看三遍都管用。关注本号不迷路。
后台回复 “资料”,领历年真题完整代码包(持续更新)。
本篇编号 GESP-054(公众号 MP-054)。完整目录与更多题解见博客专栏(公众号菜单「历史文章」)。















































































