ひどい手抜きだ…。
http://codeforces.com/contest/599/problem/C
問題
あるH*Wのグリッドがあるとする。
このグリッドのスコアは、内部のセルを一部選択してできる正方形の数の和だとする。
スコアXが与えられる。
そのようなスコアを成すグリッドサイズH*Wを求めよ。
解法
W≧Hの場合を考える。
このグリッドからは、大きさk*kの正方形は(H-k)*(W-k)個とれる。
よってH*WのグリッドのスコアF(H,W)はである。
あとはHを1~200000程度まで総当たりし、W≧Hである整数Wを列挙すればよい。
ll X; vector<pair<ll,ll> > V; void solve() { int i,j,k,l,r,x,y; string s; cin>>X; for(ll H=1;H<1601010;H++) { ll a = H*(H+1)/2; ll b = -H*(H-1)*(H+1)/6; if(X-b<=0) continue; if((X-b)%a) continue; ll W = (X-b)/a; if(H<=W) V.push_back({H,W}); if(H<W) V.push_back({W,H}); } sort(ALL(V)); cout<<V.size()<<endl; FORR(r,V) cout<<r.first<<" "<<r.second<<endl; }
まとめ
本番もう少しごちゃごちゃした式を立ててしまったため、オーバーフロー回避で10^6までしかループしなかったらWAした。