Educational Codeforces Round 38 C. Constructing Tests
問題概要
0,1からなる行列で,どのMxMの小行列をとってもいずれかの要素に0が含まれる行列をM-free Matrixという.
整数xが与えられ,1の要素数を最大化したNxNのM-free Matrixで,1の要素数がxであるようなN,Mを答えよ.
というクエリがt個与えられるので各々出力せよ.
1 <= x <= 109, 1 <= t <= 100
解法
NxN行列に対して左上から重ならないようにMxMの小行列を取っていけば求めるN,Mが
N2 - (floor(N/M))2 = x を満たしていれば良いことがわかる.
S = floor(N/M)とすると, x<=109 から N<=105ほどまで全探索すれば十分であることがわかる.
(正確には floor(N/M) ~ N/M として評価すれば上から挟める)
N,Sを見つければ,floor(N/M) = S なるMが存在するかという問題を解けば良い.
これは M=floor(N/S)として上の式を満たすかどうかを確かめれば十分であり,満たさなければ他の解を探索する.
厳密には, N = SM + k (0<=k<M)と表されるので,
SM <= N < (S+1)M <-> N/(S+1) <M <= N/S (1) から,
floor(N/(S+1)) < floor(N/S) であれば良い(*1の範囲が整数を跨いでいる)
そのようなMは複数あるかもしれないが,存在する場合はN/Sで十分となる.
メモ
難しく考えすぎて解けなかった..
