How many Nodes?

解説 (二分探索を行う解法)

$n$ 個の頂点からなる単純無向グラフは、最大で $\displaystyle \frac{n(n - 1)}{2}$ 本の辺を持ちます。 よって、$\displaystyle \frac{n(n - 1)}{2} \geq M$ なる最小の $n$ が答えです。

このような $n$ は、 $1$ 以上 $1414213563$ 以下の範囲 (これよりも広い範囲でも構わない) で二分探索を行い、不等式を満たす閾値を探索することで、見つけることができます。 探索の計算量は $O(\log M)$ ですので、全体として $O(T\log M)$ で解くことができます。

解説 (不等式を解く解法)

不等式 $\displaystyle \frac{n(n - 1)}{2} \geq M$ を解くと、 $\displaystyle n \geq \frac{1 + \sqrt{1 + 8M}}{2}$ となります。これを満たす最小の $n$ を計算すれば良いです。
しかし、浮動小数点数で右辺を計算し小数点以下切り上げを行うと、小数誤差により一部のケースで誤った答えが出てしまいます。

Python にある math.isqrt 関数 $(\sqrt{x}$ の整数部分を正確に出力する関数 $)$ などを使用し、小数誤差が発生しないよう注意して計算することでも正解することができます。

想定解

xxxxxxxxxx

T = int(input())

for _ in range(T):

    M = int(input())

    ok, ng = 1414213563, 0

    while ok - ng > 1:

        mid = (ok + ng) // 2

        if mid * (mid - 1) // 2 >= M:

            ok = mid

        else:

            ng = mid

    print(ok)    

xxxxxxxxxx

from math import isqrt

​

T = int(input())

for _ in range(T):

    M = int(input())

    x = 8*M + 1

    if isqrt(x)**2 == x:

        print((isqrt(x) + 2) // 2)

    else:

        print((isqrt(x) + 3) // 2)