【砝码称重】

【砝码称重】

题目描述 有一天,小航在小天那里无意中发现了一个天平!这个天平很奇怪,有 n 个完好的砝码,但是没有游码。小航为他的发现兴奋不已!于是他准备去称一称 WG 的东西。他准备好了 m 种物品去称。神奇的是,小航一早就知道这 m 种物品的重量,他现在是想看看这个天平能不能称出这些物品出来。小航把这个问题丢给了你。 输入格式 第一行为两个数,n 和 m 。 第...
【Farely序列与Stern-Brocot树】

【Farely序列与Stern-Brocot树】

一、 基础: 如图即为一棵Stern-Brocot树。 Stern-Brocot树第N排的真分数部分即为N阶Farey序。 1.对于每次在m1/n1,m2/n2中插入(m1+m2)/(n1+n2)构成下一排。 2.对于任意一个Farey序中连续的分数m1/n1,m2/n2,必有m1/n1<m2/n2。 3.Stern-Brocot树可以构成所有有理数...
【不可约分数】

【不可约分数】

题目描述 给出 K 和 N,请你求出第 K 小的不可约分数 p/q ,其中 0<p<q≤N 。 输入格式 输入文件第一行,是一个整数 T(T≤10),表示有 T 组测试数据。 从第二行开始,每行对应一组测试数据。 对于每组测试数据,有两个正整数 N 和 K(1≤K≤N≤100000),用一个空格隔开。 输出格式 对每组数据输出一行,即第 K 小的不...