結果

問題 No.3360 平方根の整数倍の整数部分
コンテスト
ユーザー 回転
提出日時 2025-11-15 00:34:29
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,590 bytes
コンパイル時間 247 ms
コンパイル使用メモリ 82,084 KB
実行使用メモリ 54,092 KB
最終ジャッジ日時 2025-11-15 00:34:32
合計ジャッジ時間 2,915 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 37 WA * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

# generated by AI
# Python 3 解法
import sys
from math import isqrt

def solve():
    data = sys.stdin.read().strip().split()
    if not data:
        return
    N = int(data[0]); M = int(data[1])

    if N == 1:
        print("NaN")
        return

    s = isqrt(N)
    if s * s == N:
        # 完全平方数の場合：答えは M + floor((M-1)/(s-1))
        if s == 1:
            # 既に N==1 のケースで除外済みだが安全のため
            print("NaN")
            return
        ans = M + (M - 1) // (s - 1)
        print(ans)
        return

    # N が完全平方でない場合（√N は無理数）
    # 二分探索で最小の x を求める： good(x) >= M
    # 上限の見積もり： beta = sqrt(N)/(sqrt(N)-1) が最大となるのは N=2 あたりで
    # M が最大 1e6 なので 3*M + margin を上限とする（十分余裕あり）
    lo = 1
    hi = 3 * M + 100  # 安全マージン

    def good_count(x):
        # bad = 最大の m >=0 で m^2 * N < (x+1)^2
        # つまり m^2 <= ((x+1)^2 - 1) // N
        t = (x + 1)
        # compute ((x+1)^2 - 1) // N safely with big ints
        numerator = t * t - 1
        q = numerator // N
        bad = isqrt(q)
        return x - bad

    # 二分探索（最小の x with good_count(x) >= M）
    ans = -1
    while lo <= hi:
        mid = (lo + hi) // 2
        if good_count(mid) >= M:
            ans = mid
            hi = mid - 1
        else:
            lo = mid + 1

    if ans == -1:
        print("NaN")
    else:
        print(ans)

if __name__ == "__main__":
    solve()
0