AtCoder Beginner Contest 193 C-Unexpressed_at coder 100000 99634

题目传送门

题目大意
给定一个整数n，要求找到从1到n之间的不可以用a^b(a>=2,b>=2)来表示的数字的个数。

输入格式
输入一个整数n(1<=n<=1e10)

输出格式
输出不可以用a^b形式表现的数字的个数

样例

Sample1
in:
8
out:
6
Sample2
in:
100000
out:
99634

思路
虽然n的最大是1e10，但是其实满足a^b的数不多，底数为最小的2时，2³⁴也已经大于1e10了。而且显而易见的是，就算是算最大的1e10，底数大于1e5的数也不需要考虑他们作为底数，因为大于根号n的数的平方肯定大于n。因此我们可以直接用暴力的方法来求所有a^b的个数
除此之外，我们还需要考虑一件事，就是当我们在暴力的时候可能会重复计算，比如2⁴和4²结果都是16，因此我们就使用集合来保存所有结果，这样就可以保证所有数字只出现一次，不用担心重复计算。

代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<unordered_set>
typedef long long ll;
using namespace std;

int main()
{
	ll n;
	while(scanf("%lld",&n)!=EOF)
	{
		unordered_set<ll> s;//集合
		int m = (int)sqrt((double)n);//只需要查询到根号n，因为大于根号n的数的平方肯定大于n，而指数最小为2
		for(ll i=2;i <= m;i++)//底数最小为2
		{
				ll now = i*i;
				while(now<=n)
				{
					s.insert(now);
					now*=i;
				}
		}
		ll cnt = s.size();
		printf("%lld\n",n-cnt);
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29