第1题 询问"好数" 查看测评数据信息
如果整数a = b^2 或者 a = b^3，其中正整数b>=1， 那么a就是"好数"。
即：如果a是平方数或者立方数，那么a就是"好数"。
现在有n个询问，第i个询问给出一个整数x[i]，表示询问1至x[i]范围内有多少个"好数"。
输入格式
第一行，一个整数n。1<=n<=100000。
接下来有n行，第i行有一个整数x[i]，1<=x[i]<=10^9 。
输出格式
共n行，每行一个整数。
输入/输出例子1
输入：
6
10
1
25
1000000000
999999999
500000000
输出：
4
1
6
32591
32590
23125
样例解释
无
分析：
先暴力程序，结果70分
#include <bits/stdc++.h>
using namespace std;
int n, x, ans=0;
int main()
{
scanf("%d", &n);
while (n--)
{
scanf("%d", &x);
ans=0;
map<int, int> mp;
for (int i=1; i*i<=x; i++)
if (mp[i*i]!=1) mp[i*i]=1, ans++;
for (int i=1; i*i*i<=x; i++)
if (mp[i*i*i]!=1) mp[i*i*i]=1, ans++;
printf("%d\n", ans);
}
return 0;
}
因为数据比较打，10^9，普通数组装不下，所以考虑用map
然后把可能的乘积存起来
正解：
这题首先要关注到：X虽然大，但是好数少！！不超过35000个（根号100000000=31622， 1000000000=1000^3， 显然好数最多为32622， 但会出现重复情况）
所以我们预处理好数，然后去重，排序，二分查找
代码：
注意t也要排序，否则不好去重，调试的时候就是没排序t出问题了（用set检查）
输出R
#include <bits/stdc++.h>
using namespace std;
const int N=35000;
long long n, x;
long long m1=0, t[N], m=0, a[N];
int main()
{
for (int i=1; i<=31622; i++)
t[++m1]=i*i;
for (int i=1; i<=1000; i++)
t[++m1]=i*i*i;
sort(t+1, t+1+m1);
for (int i=1; i<=m1; i++)
if (t[i]!=t[i-1]) a[++m]=t[i];
sort(a+1, a+1+m);
scanf("%lld", &n);
while (n--)
{
scanf("%lld", &x);
long long L=1, R=m, mid=0;
while (L<=R)
{
mid=(L+R)/2;
if (a[mid]>x) R=mid-1; // 因为<=都满足情况
else L=mid+1; //输出结果可以是ans，但是这行要改成 else ans=mid, L=mid+1;
}
printf("%lld\n", R);
}
return 0;
}
为什么输出的是R？分析一下即可
