全国青少年信息学奥林匹克竞赛
CCF NOI 2024
第二试
时间：2024年7月20日08:00∼13:00
题目名称 分数 登山 树形图
题目类型 传统型 传统型 传统型
目录 fraction mountain graphee
可执行文件名 fraction mountain graphee
输入文件名 fraction.in mountain.in graphee.in
输出文件名 fraction.out mountain.out graphee.out
每个测试点时限 6.0秒 2.0秒 1.5秒
内存限制 512 MiB 2048 MiB 512 MiB
测试点数目 20 20 20
测试点是否等分 是 是 是
预测试点数目 20 20 20
提交源程序文件名
对于C++语言 fraction.cpp mountain.cpp graphee.cpp
编译选项
对于C++语言 ‐O2 ‐std=c++14 ‐static
.
注
.
意
.
事
.
项（
.
请
.
仔
.
细
.
阅
.
读）
1.文件名（程序名和输入输出文件名）必须使用英文小写。赛后正式测试时将以选
手留在题目目录下的源代码为准。
2.main函数的返回值类型必须是 int，程序正常结束时的返回值必须是 0。
3.因违反以上两点而出现的错误或问题，申诉时一律不予受理。
4.若无特殊说明，结果的比较方式为全文比较（过滤行末空格及文末回车）。
5.选手提交的程序源文件必须不大于 100 KB。
6.程序可使用的栈空间内存限制与题目的内存限制一致。
7.禁止在源代码中改变编译器参数（如使用 #pragma命令），禁止使用系统结构相
关指令（如内联汇编）和其他可能造成不公平的方法。
8.选手可使用快捷启动页面中的工具 selfEval进行自测。在将待测程序（不必是全
部题目）放到题目目录下后，即可选择全部或部分题目进行自测。注意：自测有
次数限制，且自测结果仅用于选手调试，并不做为最终正式成绩。
全国青少年信息学奥林匹克竞赛 第二试 分数（ fraction）
分数（fraction）
【题目描述】
小Y和小C在玩一个游戏。
定义正分数为分子、分母都为正整数的既约分数。
定义
.
完
.
美
.
正
.
分
.
数
.
集
.
合S为满足以下五条性质的正分数集合：
1.
1
2
∈S；
2.对于
1
2
< x <2，x/∈S；
3.对于所有 x∈S，
1
x
∈S；
4.对于所有 x∈S，x+ 2∈S；
5.对于所有 x∈S且x >2，x−2∈S。
可以证明，上述五条性质确定了唯一的完美正分数集合 S。
所有完美正分数集合 S中的正分数被称为
.
完
.
美
.
正
.
分
.
数。记f(i, j)表示
i
j
是否为完
美正分数，即 f(i, j) = 1当且仅当 i与j互素且
i
j
∈S，否则f(i, j) = 0。
小C问小Y：给定n, m，求所有分子不超过 n，分母不超过 m的完美正分数的个
数，即求
∑
n
i=1
∑
m
j=1
f(i, j)。
时光走过，小 C和小Y会再遇见
全国青少年信息学奥林匹克竞赛 CCF NOI 2024 第二试 day2真题