#622. 数方格
数方格
Description
为了提升市民的生活品质,绍兴市打算新建一个广场,为了美观,要求这个广场是正方形的。目前正在规划当中,正方形的大小和位置都在热烈的讨论之中,小明同学也正在研究这项规划。现在已知可用于建造广场的区域是一个矩形,它由若干个1*1的单位正方形构成,如下图所示的就是一个4*6的矩形区域。
现要求正方形广场必须建在给定的矩形范围内,广场边线不能跨过任意一个单位正方形的内部,只能与正方形边线重合,如针对上图中的矩形,以下4种正方形均为可行方案(当然不止这些方案):
市民们提出了很多建造广场的方案,现在小明想要知道,到底有多少种不同的方案可供领导选择?请你设计一个程序,来计算一下建造广场的最多可行方案数。
Input Format
只有一行,有两个整数n和m,表示用于建造广场区域的长和宽。对于10%的数据,n=1,1<=m<=100,
对于60%的数据,1<=n<=m<=100。
对于100%的数据,1<=n,m<=1000。
Output Format
也只有一行,有一个整数,表示建造广场的可行方案数。
1 5
5