必做
蛋糕
分析
题意分析
分析
思路分析
分析
代码分析
题目描述
小码君和他的同学,一共 k 个人,正在庆祝生日。他们一共定了 n 个长方形蛋糕,第 i 个蛋糕的尺寸为 H
i
× W
i
。为了让每个人吃到一样的蛋糕,小码君想要把这 n 个蛋糕切成 k 块分给在场的每个人。切出的蛋糕需要满足:
大小是一样的
都是正方形,且边长是整数
提示
数据范围:1≤n,k≤100000,1≤H
i
,W
i
≤100000
样例解释:
2 个蛋糕,至少分成 10 份。为了保证每一份都是正方形,则分出的蛋糕边长最大为 2。
6∗5的蛋糕可以分 6 个 2∗2 的蛋糕,5∗6的蛋糕可以分 6 个 2∗2 的蛋糕,一共 12 个完全可以满足一人一个。
输入格式
第一行包含两个整数 n 和 k ,分别表示蛋糕的数量和庆祝的人数。
之后的 n 行每行包含两个整数 H
i
和 W
i
,中间用一个空格隔开,表示蛋糕的尺寸。
输出格式
输出切出的正方形蛋糕最大可能的边长。
样例组输入#1
2 10
6 5
5 6
样例组输出#1
2