SRM 522 Div2 Hard CorrectMultiplicationTwo

問題

http://apps.topcoder.com/stat?c=problem_statement&pm=11609&rd=14547
a * b = cという等式が与えられる。しかしこの等式は成り立っていないのでa,b,cをA,B,Cに書き換えてA * B = Cが成り立つようにしたい。の最小値はいくつか。

1 <= a,b,c,A,B,C <= 1000000

やりかた

Aを1から1000000まで試してみる。B = c / Aなのでこの前後±2くらい調べてあげればいい。
intのオーバーフローに注意。

以下ソース。

class CorrectMultiplicationTwo {
public:
  ll sub(int x, int y, int z){
    ll a = (ll)(z - x * y);
    return a > 0 ? a : -a;
  }
  int getMinimum(int a, int b, int c) {
    ll result = INF;
    if(b > a) swap(a, b);
    for(int i = 1; i <= 1000000; i++){
      int j = c / i;
      for(int d = -3; d <= 3; d++){
	if(j + d > 0)
	  result = min(result, abs(a - i) + abs(b - (j + d)) + sub(i, j + d, c));
      }
    }
    return result;
  }
};

900はだいぶできるようになっていると思う。1000との違いが大きい。

中だるみがはげしい。ペースがどんどん落ちている。