p1028 [noip2001 普及组] 数的计算
时间: 2023-04-24 20:05:46 浏览: 167
数的计算
题目描述
给定一个正整数 n,求有多少个 k 满足 k^2 ≤ n。
输入格式
一个整数 n。
输出格式
一个整数,表示满足条件的 k 的个数。
输入样例
10
输出样例
3
算法1
(暴力枚举) $O(\sqrt{n})$
枚举从 1 到 $\sqrt{n}$ 的整数,统计满足条件的个数。
时间复杂度
参考文献
python3 代码
C++ 代码
算法2
(二分查找) $O(\log n)$
二分查找满足 k^2 ≤ n 的最大的 k 值,然后返回 k。
时间复杂度
参考文献
C++ 代码
阅读全文