夜雨聆风学习资料网

ARTICLE · 1377739

GESP 2024年12月 真题 奇妙数字 完整题解(数论)

GESP 2024年12月 真题 奇妙数字 完整题解(数论)
【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 的因子) 。

小杨希望集合包含的奇妙数字尽可能多, 请你帮他计算出满⾜条件的集合最多包含多少个奇妙数字。

样例
输入
128
输出
3
题解正文

这题光看代码容易绕进去,先找个生活里的比方,比方对了,代码就是照着抄。

今天刷 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 相加即为答案。

读入数据 → 逐个处理并累加 → 按格式输出

比方和代码是一一对应的:比方里先说清「有几样东西」,对应代码里的变量;比方里「一个一个过」,对应那个循环。

四、完整代码

建议先自己写二十分钟,卡住了再看。对着抄一遍的效果,比不上自己错一遍。

#include <bits/stdc++.h>
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";  // 输出
}
五、两段代码,两处对应

代码在上面,这里只挑最关键的两段讲,其他都是顺手写的。

第一段,把数据读进来。

    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);
        }
    // …(这段后面还有,见上面的完整代码)

这段是整道题唯一需要想的地方,也是数论的落点。看循环时只问三句:从哪开始、到哪结束、每次加几。三句都对,这段就没错。

六、用样例走一遍这个比方

代码写完不算完,得验。验也有顺序,从样例开始。

样例输入

128

样例输出

3

按这个顺序走一遍,跟上面那个比方对上:

  1. 拿样例对一遍,输出和题目给的一模一样。
  2. 把数据压到最少,边界情形下答案仍然对。
  3. 看最后一行,结尾有换行,不多输出空行。
七、打比方容易带偏的三个点

按危险程度从高到低排,第一条最常见:

  1. 累加结果溢出——写成 int sum = 0; 就错,应该是 long long 声明累加变量。
  2. 下标起点错位——写成 for (i = 0; i < n; i++) 存 a[i] 就错,应该是 for (i = 1; i <= n; i++) 存 a[i]。
  3. 输出格式不符——写成 cout << ans; 就错,应该是 cout << ans << "\n";。
  4. 多组数据没清空——写成 全局数组直接用 就错,应该是 每组数据前 memset 或重新赋值。
八、记住这个比方就够了

这题的经验压缩成三行,考前扫一眼就够。

  • 这题考的:数学 数论——把题目条件一句一句翻译成代码,不添不减。
  • 要记住的:取模题里乘法最容易溢出,乘之前先把两个因子都转成 long long。
  • 下一步:拿同场次另一道题练手,换题型不换节奏,手感就稳了。

这题就讲到这。同一场次的题我会接着更,跟着刷完一整场,你对这个级别的题感就出来了。


系列导航
  • 本文属于《GESP 真题题解》系列,第 50 篇,真题按年份持续补齐,每篇都带完整可编译代码,题号可在 ACGO 直接提交验证。
  • 还没动笔的话,先自己写一遍再回来看踩坑总结,比直接照抄代码收获大。
  • 想跟完整系列的朋友点个关注,更新会第一时间推送。
  • 本系列合集目录(按年份/组别排序)
写在最后

GESP 的坑多半在边界和读题上。这道数论题把该注意的点都列在上面的表里了,提交前逐条过一遍。

今天想问你:这题的坑你踩了几个?踩得最多的那个,评论区报个数,我看看大家集中在哪。

把这篇转给一起刷题的同学,两个人对着讲一遍思路,比一个人看三遍都管用。关注本号不迷路。

后台回复 “资料”,领历年真题完整代码包(持续更新)。

本篇编号 GESP-054(公众号 MP-054)。完整目录与更多题解见博客专栏(公众号菜单「历史文章」)。

回首页,搜索你想要的文档

在首页搜索框输入关键词,快速定位资料

文库首页搜索指引 立即搜索

相关学习资料