#6957. 康托表

康托表

题目背景

康托是一名数学家,他证明了一个重要的定理,需要使用一张表:

$$\begin{array}{ccccccc} 1/1 & 1/2 & 1/3 & 1/4 & 1/5 & \cdots\\ 2/1 & 2/2 & 2/3 & 2/4 & 2/5 & \cdots\\ 3/1 & 3/2 & 3/3 & 3/4 & 3/5 & \cdots\\ 4/1 & 4/2 & 4/3 & 4/4 & 4/5 & \cdots\\ 5/1 & 5/2 & 5/3 & 5/4 & 5/5 & \cdots\\ \cdots&\cdots&\cdots&\cdots&\cdots&\cdots\\ \end{array} $$

这个表的规律是:

  • 从上到下:每一行的分子依次增大;
  • 从左到右:每一列的分母依次增大。

康托以一种不重复、不遗漏的方式,将表上所有数字列举了出来。方法如下:从左上角的 1/11/1 出发, Z 字形扫描,其中:

  • 第一项是 1/11/1
  • 第二项是 1/21/2、第三项是 2/12/1
  • 第四项是 3/13/1,第五项是 2/22/2,第六项是 1/31/3
  • 接下来几项分别是:
1/4, 2/3, 3/2, 4/1, 5/1, 4/2, 1/4, ~2/3, ~3/2, ~4/1, ~5/1, ~4/2, ~\cdots

题目描述

给定一个分数 a/ba/b,请计算该分数在康托表中排名第几。

输入格式

两个整数:aabb,表示一个分数 a/ba/b

输出格式

单个数字:表示输入分数在康托表中的名次。

2 4
14
1 4
7

数据范围

  • 对于 50%50\% 的分数,1a,b1001\leq a,b\leq 100
  • 对于 100%100\% 的分数,1a,b100001\leq a,b\leq 10000