题解：洛谷 P1458 [USACO2.1] 顺序的分数 Ordered Fractions

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】洛谷P1458 [USACO2.1] 顺序的分数 Ordered Fractions - 洛谷【题目描述】输入一个自然数n nn对于一个最简分数a / b a/ba/b分子和分母互质的分数满足1 ≤ b ≤ n , 0 ≤ a / b ≤ 1 1≤b≤n,0≤a/b≤11≤b≤n,0≤a/b≤1请找出所有满足条件的分数。这有一个例子当n 5 n5n5时所有解为给定一个自然数n nn请编程按分数值递增的顺序输出所有解。注1、0 00和任意自然数的最大公约数就是那个自然数。2、互质指最大公约数等于1的两个自然数。【输入】单独的一行一个自然数n nn【输出】每个分数单独占一行按照大小次序排列【输入样例】5【输出样例】0/1 1/5 1/4 1/3 2/5 1/2 3/5 2/3 3/4 4/5 1/1【核心思想】问题分析给定自然数n nn要求输出所有满足0 ≤ a ≤ b ≤ n 0 \le a \le b \le n0≤a≤b≤n且gcd ⁡ ( a , b ) 1 \gcd(a,b)1gcd(a,b)1的最简分数a / b a/ba/b并按数值递增排列。该序列正是法里序列Farey SequenceF n F_nFn​其核心性质是序列中任意相邻两项a / b a/ba/b与c / d c/dc/d满足b c − a d 1 bc-ad1bc−ad1。算法选择法里序列递推利用相邻两项的中项性质直接按顺序生成下一个分数无需枚举再排序。整数递推公式已知相邻两项a / b c / d a/b c/da/bc/d下一项为( k c − a ) / ( k d − b ) \big(kc-a\big)/\big(kd-b\big)(kc−a)/(kd−b)其中k ⌊ ( n b ) / d ⌋ k \lfloor (nb)/d \rfloork⌊(nb)/d⌋。关键步骤初始化设前两项为a / b 0 / 1 a/b 0/1a/b0/1c / d 1 / n c/d 1/nc/d1/n。顺序生成当c ≤ n c \le nc≤n时循环计算k ⌊ ( n b ) / d ⌋ k \lfloor (nb)/d \rfloork⌊(nb)/d⌋。下一项e / f ( k c − a ) / ( k d − b ) e/f (kc-a)/(kd-b)e/f(kc−a)/(kd−b)。输出当前项c / d c/dc/d。滑动窗口令a / b ← c / d a/b \leftarrow c/da/b←c/dc / d ← e / f c/d \leftarrow e/fc/d←e/f。边界处理首项0 / 1 0/10/1在循环前直接输出末项1 / 1 1/11/1会在循环中自然生成并输出。时间/空间复杂度时间复杂度O ( ∣ F n ∣ ) O(|F_n|)O(∣Fn​∣)即O ( n 2 ) O(n^2)O(n2)因为法里序列长度约为3 n 2 / π 2 3n^2/\pi^23n2/π2。空间复杂度O ( 1 ) O(1)O(1)仅需维护两对相邻分数的分子分母。法里序列的核心思想相邻互素性若a / b a/ba/b与c / d c/dc/d在F n F_nFn​中相邻则b c − a d 1 bc-ad1bc−ad1保证两数之间无其他分母≤ n \le n≤n的分数。中项跳表递推公式e / f ( k c − a ) / ( k d − b ) e/f(kc-a)/(kd-b)e/f(kc−a)/(kd−b)实质是用最大允许倍数k kk控制新分母不超过n nn从而直接“跳”到下一个最简分数。避免浮点比较全程使用整数运算规避浮点精度问题结果严格有序。在线性空间内顺序输出不需要存储所有分数再排序生成一个输出一个。适用于按顺序枚举区间[ 0 , 1 ] [0,1][0,1]内所有最简分数的问题。【解题思路】【算法标签】#普及- #约数【代码详解】#includebits/stdc.husingnamespacestd;intn,mark;structnode{// 定义分数结构体doubleres;// 分数结果注意是double类型inta,b;// 分子和分母}fra[25600];// 按照160*160的最大范围开辟结构体数组intgcd(inta,intb)// 最大公约数模板背就完了{intra%b;while(r!0){ab;br;ra%b;}returnb;}boolcmp(node x,node y)// 比较函数按照res从小到大排序{returnx.resy.res;}intmain(){cinn;// 输入nfra[0].res0;// 数组第1个res为0fra[0].a0,fra[0].b1;// 分子为0分母为1mark1;// 定义计数器for(inti1;in;i){// 从1遍历至nfor(intji;jn;j){// 从i遍历至nif(gcd(i,j)1){// 如果分子和分母的最大公约数为1fra[mark].res1.0*i/j;// 记录分数结果fra[mark].ai,fra[mark].bj;// 以及分子和分母mark;// 计数器自增1}}}sort(fra,framark,cmp);// 对结构体数组按照res从小到大方式排序for(inti0;imark;i){// 依次输出mark-1因为存完最后一个mark仍自增了1个分子和分母coutfra[i].a/fra[i].bendl;}return0;}【运行结果】5 0/1 1/5 1/4 1/3 2/5 1/2 3/5 2/3 3/4 4/5 1/1