链接:https://codeforces.com/contest/1029/problem/F
思路:i从1开始到根号(a+b)进行遍历,维护一个最小值,当某个值是a或b的因子时,更新这个最小值为(a或者b)/i,表示要放一个矩形在里面所需要的最小的边,如果当(a+b)%i==0时且最小值小于(a+b)/i,就表示可以放下一个矩形,从而更新一下周长的最小值,一直到遍历结束即可。这个题必须要这样从小到大遍历,不然将面临一个大矩形里面放能否放一个a或者b的矩形这样的问题,无法在常数的时间内解决,复杂度会加一个维度,从小到达遍历保证每一种能放的情况都考虑到了,从而一定会找到最优解。
代码:
#include<bits/stdc++.h>
using namespace std;
long long a,b;
int main(){
scanf("%I64d%I64d",&a,&b);
long long i = sqrt(a+b+0.1);
long long minv = 1e18,res = 1e18;
for(long long j=1;j<=i;j++){
if(a%j==0)minv = min(minv,a/j);
if(b%j==0)minv = min(minv,b/j);
if((a+b)%j==0&&minv<=(a+b)/j)res = min(res,2*j+2*(a+b)/j);
}
printf("%I64d\n",res);
return 0;
}