TopCoder SRM 547 Div1 Medium RectangularSum

問題

幅h, 高さwのグリッドがある。
グリッドには
0 1 2 ... w-1
w w+1 w+2 ... 2w-1
...


のように数字が書かれている。
このグリッドの長方形の部分で、書かれている数字の総和がSであるような部分のうち、
最も面積が小さいものの面積を求めよ。


そのような長方形が存在しない場合-1を返せ。

制約条件

h, w≦10^6
S≦10^12

方針

左上をの数字をxとして、高さa, 幅bの長方形に書かれている数字の和は、
x, a, b(とw, h)の簡単な式で表すことが出来る。


表すと、
2S = a * b * (〜)という形になり、
a, bは2Sの約数に限られることがわかる。
したがって、このようなa, bを、2Sの約数を列挙して探せばよい。


あまり適当に約数を探すとTLEになってしまうが、
2Sを素因数分解してからa, bを組み立てれば、最悪200msくらいで終わる。

ソースコード

int n, h, w;
ll S, p[100], e[100], ans;

void rec(ll a, ll b, int cur){
	if(cur == n){
		ll x = 2 * S / a - w * b * (a - 1) - b * (b - 1);
		if(x < 0 || x % (2 * b)) return;
		x /= 2 * b;
		
		ll r = x / w, c = x % w;
		if(0 <= r && r + a <= h && 0 <= c && c + b <= w)
		ans = min(ans, a * b);
		return;
	}
	rep(i, e[cur] + 1){
		ll nb = b;
		rep(j, e[cur] - i + 1){
			rec(a, nb, cur + 1);
			nb *= p[cur];
		}
		a *= p[cur];
	}
}

class RectangularSum {
  public:
  long long minimalArea(int height, int width, long long S) {
  	::S = S; h = height; w = width;
  	
  	n = 0;
  	ll s = 2 * S;
		for(ll i = 2; i * i <= s; i++) if(s % i == 0){
			int c = 0;
			while(s % i == 0) s /= i, c++;
			p[n] = i;
			e[n++] = c;
		}
		if(s > 1) p[n] = s, e[n++] = 1;
		ans = inf;
		rec(1, 1, 0);
		
		return ans == inf ? -1 : ans;
  }
};