問題

f:id:trsing:20200711111311p:plain

考えたこと

ペアの組み合わせとしては $[1 \cdots \sqrt{AB} )$ と $[1 \cdots \sqrt{AB} )$ 、 $[1 \cdots \sqrt{AB} )$ と $[\sqrt{AB} \cdots$ だけど後者のペアをなるべく作ればペアの数を増やせる。

前提条件

$r \leq s,\,\, rs \lt AB,\,\,\,B \lt A$

① $1: (r-i)(s+i)=rs-(s-r)i-i^{2} \leq rs \lt AB (0 \leq i)$

$r-i=B のとき (r-i)(s+i)=B(s+r-B)\lt AB$
よって
② $r-b \lt A-s$

$r= \lfloor \sqrt{AB} \rfloor$ とおく

rが平方数の場合

$r*r=AB$ なので $r$ の組を作れません。 $r$ 未満は使用できるので $r-1$ 個の組を二つ作れます*1。

$A \neq B$ の場合、 $A,B$ が使えなため $-1$ *2して $r-1+r-1-1$ 。
$A=B$ の場合はそのまま $r-1+r-1$

rが平方数でない場合

$r(r+1)\lt AB$ の場合、 $r$ 個の組を二つ作れます。
そうでない場合、 $r$ 個の組と $r-1$ 個の組を作れます*3。 A,Bが使えないため $-1$ 。よって前者は $r+r-1$ 後者は $r+r-1-1$

コード

static long Calc(long A, long B)
{
    if (A == B)
        return A - 1 + B - 1;

    var lim = A * B;
    var r = (long)Sqrt(lim);
    if (lim < r * r) --r;
    if ((r + 1) * (r + 1) < lim) ++r;
    if (r * r == lim)
        return r - 1 + r - 1 - 1;
    var a = r + r - 1 - 1;
    if (r * (r + 1) < lim)
        ++a;
    return a;
}