Leave-绿光

测试数据来自 system/1279

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

背景

期待这一份幸运,和一份冲劲,多么奇妙的际遇……。燕姿在演唱完绿光这首歌后,出给了姿迷一个考题。

北欧有一个传说!
人一生中能看见绿光!
他就一生都可以得到幸福!

描述

燕姿唱完这首歌,天上降落了一道绿光,在地上形成了一个矩形的映射,矩形的长为a,宽为b。燕姿向姿迷出了一个考题,谁能够把这个矩形绿光阵分成若干个正整数的正方形,谁的正方形边长之和最小,他就将得到燕姿的一个合影。姿迷们都很想得到合影,可是怎么分才最小呢?大家都束手无策,现在,这个问题交给你了。

歌迷X:呜呜呜,俺的语文不好,听不懂你在讲什么。

燕姿:别怕,其实这个问题可以简化为……

将边长为正整数a,b的长方形划分成若干边长均为正整数,每个正方形的边均平行于矩形的相应边,试求这些正方形边之和的最小值MIN。

(如果这个长方形可以分成N个正方形,其中每个边长为Ai,那么MIN=A1+A2+^^^+AN
注意,数组A中的元素可能相等)

格式

输入格式

一共10行
每行两个正整数,Ai,Bi

对于30%的数据,Ai,Bi<maxint
对于100%的数据,Ai,Bi<maxlongint;

输出格式

一共10行
每行一个整数,输出MINi

样例1

样例输入1

1 1
2 1
3 1
4 1
5 1
6 1
7 1
8 1
9 1
10 1

样例输出1

1
2
3
4
5
6
7
8
9
10

限制

每点1s

提示

对于样例,可全分长边长为一的正方形,并且可以证明找不到比其更优的分割方法;
加油吧,为了得到燕姿的合影(#17)

来源

孙燕姿
图片

小兰赛 2019/11/9

未参加
状态
已结束
规则
OI
题目
4
开始于
2019-11-09 09:00
结束于
2019-11-09 12:00
持续时间
3.0 小时
主持人
参赛人数
13