立方

问题描述

今年乐乐开始学编程了，上几天刚刚解决了一个平方数的问题，问题是这样的：随便告诉你一个不超过 1 个亿的正整数，请你算出不超过该数的所有立方数的个数。
但是，如果这个超过 1 亿，是一个 18 位正整数，或 28 位的正整数呢？
乐乐不会算，你会吗？

输入格式

只有一行且只有一个正整数：n

输出格式

只有一行且只有一个正整数：不超过 n 的平方数个数

样例输入

100

样例输出

提示

1*1*1 = 1　　 2*2*2 = 8
3*3*3 = 27　　4*4*4 = 64
5*5*5 = 125 但是 125 > 100

数据范围

对于30%的数据，1≤n≤10⁸
对于70%的数据，1≤n≤10¹⁸
对于100%的数据，1≤n≤10²⁸

题解

最暴力的算法是直接从1枚举到n，验证每一个数是不是立方数

事实上，越大的数，相邻两个立方数的差越大，所以n越大就会浪费越多的时间

而计算机1秒能运行的次数最多不超过1亿次，n的最大值有28位数，一个一个数枚举会超时超的很严重

换一个思路，我们可以通过枚举立方数的立方根直接找到立方数

从1开始，每一个数都对应着唯一一个立方数

即，1对应的立方数是1，2对应的立方数是8，3对应的立方数是27，4对应的立方数是64，……

所以我们可以通过枚举1,2,3,4，…… 直接找到对应的立方数1,8,27,64，……

这样我们就可以省掉验证2,3,4，……，7,9,10，……26,28,29，……，63,65，……是不是立方数的时间。显然，n越大省的时间越多

我们知道最大的立方数不会超过n，所以我们只要枚举到n的立方根就可以了，这样比最开始的一个数一个数枚举省了很多时间

但是别忘了计算机1秒能运行的次数最多不超过1亿次，而一个28位数开立方也有9位数，还是会超过1亿次

观察上述算法，我们发现，从1到n的立方根的每一个数都对应一个立方数，所以，不超过n的立方数的个数其实就是n的立方根（下取整）

介绍一下C++自带的求立方根的函数cbrt（），在<cmath>的头文件里（C语言好像没有？）或者直接万能头文件<bits/stdc++.h>

还有一个要注意的是C和C++最大的整型long long最大值也只有18位数，所以要用double存n

然后代码并不是很长。。。。

 1 #include <cstdio>
 2 #include <cmath>
 3 #define ll long long
 4 double n;
 5 int main()
 6 {
 7     scanf("%lf",&n);
 8     ll x=cbrt(n);
 9     printf("%lld
",x);
10     return 0;
11 }