数学问题

ACM练习题

题目地址

数学问题
时间限制：2000/1000 MS（Java / Others）内存限制：32768/32768 K（Java / Others）
总提交：1321接受提交：476

问题描述
给定一个正整数n，请计算k个满足多少正整数 ķ^k≤ N。

输入
没有超过50个测试用例。

每种情况只包含一行中的积分整数n。

1 ≤ N ≤ 1e18

产量
对于每个测试用例，输出整数表示正整数k满足的数量 k^k≤ N 在一条线上。

样品输入
1
4

样品输出
1
2

错误答案：

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;


int main() {
    // 正整数
    long long n;
    int k = 1, sum = 0;
    while (scanf("%I64d", &n) != EOF && n >= 1 && n <= 1e18)
    {
        while (k <= n)
        {
            if (pow(k, k) <= n)
            {
                sum++;
                k++;
            }
            else {
                break;
            }
        }
        printf("%d\n", sum);
        sum = 0;
        k = 1;
    }
    return 0;
}

正确答案：

#include<iostream>
#include<cmath>
using namespace std;
long long a[20];
void deal()
{
    for (int i = 1; i <= 15; i++) // 计算k的k次方
    {
        long long result = 1;
        for (int j = 1; j <= i; j++)
        {
            result *= i;
        }
        a[i] = result;
    }
    a[16] = (long long)1e18 * 9; // 界限是1e18
}
int main()
{
    deal();
    long long n;
    while (cin >> n)
    {
        for (int i = 1; i <= 16; i++)
        {
            if (a[i] > n)
            {
                cout << i - 1 << endl;
                break;
            }
        }
    }
}

出错原因：

1. 你会发现两种方法的最大不同：

• 第一种是每一次算出一个k的k次方来和n比较，使用pow()函数计算k的k次方
• 第二种是把k^k(1<=k<=15)放在一个数组中，并且在最后一个数中放a[16] = 1e18 * 9计算k的k次方的函数是自己写的

2. 第二种成功的方法为什么(1<=k<=15)，并且在数组下标16位放1e16*9：

• 15^15 = 437,893,890,380,859,375 ，一共18位，但是比1e18小
• 16^16 = 18,446,744,073,709,511,616 ，一共20位, 比1e18大
• long long的最大值：9,223,372,036,854,775,807，一共19位
• 这样就确定了k的范围，并且解释了为什么在数组下标16位放1e16*9
• 当然你也可以这样写，只要最大的数字比1e18大就好

a[16] = (long long)1e18 + 1; // 界限是1e18

• 但是这样不是最严谨，尽量放大一点是最严谨的

2. 重点要解释的问题，使用pow()函数为什么会出错：

pow()函数返回的是double类型的数，使用pow()函数打印15的15次方你会发现：

再拿计算器计算

两个结果不一样，对比下面两张图你就会发现

当数字大到15^15时两个计算的结果就不同，所以这就导致了第一种方法出现错误答案的原因！

总结：

解题时注意关注数据类型的取值范围和精度问题，还有题目中的数据的取值范围。