A new problem

sheldenwade · 发表于 2011-10-11 15:07:58

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要登录才可以下载或查看，没有账号？欢迎注册

×

Given an big integer N, how to judge that whether there exists an integer m where N=m*m with O(1) time complexity.
For example, for the number 9, there exists an integer 3 that 3*3=9.
For the number 18, we cannot find the proper number.

PS: MUST BE O(1) time complexity , which means your method can be done in constant step no matter how big the number N is.
MUST TAKE IT INTO CONSIDERATION that N is a very very large integer.

g99 · 发表于 2011-10-11 16:22:08

O(1)不太可能吧，依据完全平方数的性质可以判断一些数，但是不能判断所有数

g99 · 发表于 2011-10-11 16:25:15

不知道这样算不算：
先算$m=\sqrt{N}$
然后判断$m*m$是否等于$N$，但是对于大数就不行了

账号		自动登录	找回密码
密码			欢迎注册

[原创] A new problem

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。