ABC193 C - Unexpressed（思维+暴力）_[abc193c] unexpressed

题意：

解法：

考虑计算可表示为a^b的数的个数,最后用n去减即可.
因为题目要求b>=2,那么a最大为sqrt(n),也就是只有1e5.

直接在[1,sqrt(n)]中枚举a,然后从2开始枚举b,
当a^b>n时跳出,否则标记a^b.

这样做的话总循环的数很少,
因为当b=2时,底数<=1e5种,
当b=3时,底数<1e3种,
当b更大的时候,底数数量更少.

因此枚举的话,内存和时限都不会超.
1
2
3
4
5
6
7
8
9
10
11
12

code：

#include <bits/stdc++.h>
#define int long long
using namespace std;

signed main(){
    ios::sync_with_stdio(0);
    int n;cin>>n;
    map<int,int>mp;
    for(int i=2;i*i<=n;i++){
        int t=i;
        while(1){
            t*=i;
            if(t>n)break;
            mp[t]=1;
        }
    }
    cout<<n-mp.size()<<endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19