TopCoder SRM 522 Div1 Medium CorrectMultiplication

問題

a,b,cという三つの数を変えてA * B = Cが成り立つようにしたい。
このとき、|A - a| + |B - b| + |C - c|の最小値を求めよ。

制約条件

a,b,c≦10^9

方針

Cをc-1500≦C≦1500くらいだろうと決めつけて、
それぞれに対して素因数分解を行い最もよいa,bを行うという嘘解法をしたら通った。

何でこれで通るのか謎。

ソースコード

class CorrectMultiplication {
  public:
  long long getMinimum(int a, int b, int c) {
    ll ans=1ll<<60;
    if(a>b)swap(a,b);
    for(int C=max(0,c-1500);C<c+1500;C++){
      for(int x=1;x*x<=C;x++){
        if(C%x==0){
          int A=x, B=C/x;
          if(A>B)swap(A,B);
          ans=min(ans,(ll)abs(A-a)+abs(B-b)+abs(C-c));
        }
      }
    }
    return ans;
  }
};