def isqrt(n):
"""纯整数平方根(牛顿迭代法),无任何浮点运算"""
if n < 0:
raise ValueError("Square root not defined for negative numbers")
if n == 0:
return 0
# 初始猜测值使用位运算,避免浮点转换
x = 1 << ((n.bit_length() + 1) // 2)
while True:
y = (x + n // x) // 2
if y >= x:
return x
x = y