第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?分析一下即可
标签:输出,好数,int,询问,long,T1,整数,2023 From: https://www.cnblogs.com/didiao233/p/17891327.html