天真的解决方案是对所有对进行 O(sqrtRoot of N) 搜索，但应该有更智能的解决方案...
我被暗示使用线程二叉树...有什么想法吗？
最佳答案
如果您需要一个大致数字，并且 N 足够大，您可以在 O(1) 中回答:如果您对非负 (m,n) 对感兴趣，只需回复 pi*N*N/4；如果允许否定回复 pi*N*N。
注意到每对 (m,n) 使得 m*m+n*n < N, m>0, n>0 对应于半径为 sqrt(N) 的圆盘内右上象限内的一个点。这种四分之一圆盘的面积是 pi*N*N/4。每个点 (m,n) 对应一个 1x1 的正方形。因此，您可以预期大约 pi*N*N/4 个这样的对覆盖四分之一圆盘的所有区域。
如果您需要一个精确的数字，那么我不知道有任何算法会比 O(sqrt(N)) 运行得更快。
关于algorithm - 给定一个数字 N，如何计算满足 m*m + n*n < N 的所有 m 和 n int 对的数量？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/21638462/