p1028 [noip2001 普及组] 数的计算

题目描述

给定一个正整数 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++ 代码

相关问题

P1028 [NOIP2001 普及组] 数的计算C++

题目P1028是NOIP（全国青少年信息学奥林匹克联赛）2001年的普及组比赛题目，通常涉及基础算法和数据结构。这个题目可能是一个关于数的计算问题，例如计算一系列数字的操作，比如加法、乘法、最大值、最小值等。在C++中，解决这类问题可能需要使用循环、条件语句以及一些基本的数据类型，如整型。

例如，如果问题是求一组整数的平均值，你可以这样做：

#include <iostream>
using namespace std;

double calculateAverage(int arr[], int size) {
    double sum = 0;
    for (int i = 0; i < size; i++) {
        sum += arr[i];
    }
    return sum / size;
}

int main() {
    int numbers[] = {1, 2, 3, 4, 5};
    int arraySize = sizeof(numbers) / sizeof(numbers[0]);
    double average = calculateAverage(numbers, arraySize);
    cout << "The average of the numbers is: " << average << endl;
    return 0;
}

在这个例子中，`calculateAverage`函数接收一个整数数组和它的大小，然后计算并返回平均值。

如果你能提供具体的题目描述或更详细的要求，我可以给出更精确的答案。

洛谷P1029 [NOIP2001普及组]最大公约 数和最小公倍数问题

洛谷P1029题是关于求两个非负整数的最大公约数（GCD）和最小公倍数（LCM）的问题。这个问题通常使用辗转相除法（也称为欧几里得算法）来求最大公约数，然后利用最大公约数来求最小公倍数。

最大公约数是指两个或多个整数共有约数中最大的一个，而最小公倍数是指能被两个或多个整数整除的最小的正整数。对于任意两个正整数a和b，它们的最大公约数记为gcd(a, b)，最小公倍数记为lcm(a, b)，它们满足以下关系：

1. gcd(a, b) * lcm(a, b) = a * b

要解决这个问题，首先需要编写一个求最大公约数的函数，然后根据最大公约数和原来两个数的乘积计算出最小公倍数。以下是用C++语言实现的一个示例代码：

#include <iostream>
using namespace std;

// 函数：计算最大公约数
int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

// 函数：计算最小公倍数
int lcm(int a, int b) {
    return a / gcd(a, b) * b;
}

int main() {
    int a, b;
    cin >> a >> b;
    cout << gcd(a, b) << endl;
    cout << lcm(a, b) << endl;
    return 0;
}

在实际使用中，用户需要输入两个非负整数，程序会输出它们的最大公约数和最小公倍数。