欢迎访问==> 【考研OR保研】机试题
题目描述
设一个正整数既是平方数又是立方数时,称之为 Special 数。
输入整数 $n$,请你计算 $1$ 到 $n$ 中包含的所有 Special 数的个数。
输入格式
第一行包含整数 $T$,表示共有 $T$ 组测试数据。
每组数据占一行,包含一个整数 $n$。
输出格式
每组数据输出一行,一个结果。
数据范围
$1 \\le T \\le 100$,
$1 \\le n \\le 10^9$
输入样例:
2
1
64
输出样例:
1
2
C++ 代码
/*
单词积累:【平方:square】【立方:cubic】
*/
#include <bits/stdc++.h>
using namespace std;
int T, n;
unordered_set<int> square, cubic;
int main()
{
//将【1 ~ 1e9】中的平方数和立方数预处理存在哈希表中
for(int i = 1; i * i <= 1e9; i ++) square.insert(i * i);
for(int i = 1; i * i * i <= 1e9; i ++) cubic.insert(i * i * i);
cin >> T;
while(T -- )
{
cin >> n;
int cnt = 0;
//即在square中也在cubic中,同时满足小于等于n的数满足条件
for(auto t : square)
{
if(cubic.count(t) && t <= n) cnt ++;
}
cout << cnt << endl;
}
return 0;
}
枚举cubic中的数会快很多
甚至不用枚举两个set,符合两个条件的数总共只有31个