TopCoder SRM 522 Div1 Medium CorrectMultiplication

Div2 Hardと同じ問題だけどDiv1 Mediumの方が制限が厳しいので、こちらに挑戦。
知らずに先にDiv2をやったため、似たような問題を２回解くことに。
http://community.topcoder.com/stat?c=problem_statement&pm=11604

問題

３つの整数a,b,cが与えられる。
A*B=Cを満たす整数のうち、abs(A-a)+abs(B-b)+abs(C-c)の最小値を答えよ。

解法

aとbは対称な関係なので、acの場合、逆にaを小さくするのが一番早い。

よって、Aを1～√c程度総当たりし、Bをint(c/a)周辺を調べるようにし、得られたC=A*Bに対しabs(A-a)+abs(B-b)+abs(C-c)の最小値を取ればよい。

class CorrectMultiplication {
	public:
	long long getMinimum(int a, int b, int c) {
		ll mi=a+(ll)b+c;
		if(a>b) swap(a,b);
		
		for(ll A=1;A<=sqrt(c)*2;A++) {
			for(ll B=c/A-2;B<=c/A+2;B++) {
				if(B<0) continue;
				ll C=A*B;
				mi=min(mi,abs(A-a)+abs(B-b)+abs(C-c));
			}
		}
		return mi;
	}
};

まとめ

割と簡単なMediumだけど、これ450ptだね。