AtCoder - abc193_c 思维，枚举_at_abc193_e

AtCoder - abc193_c

题目
Problem Statement
Given is an integer N. How many integers between 1and N (inclusive) are unrepresentable as a b, where a and b are integers not less than 2?

Constraints N is an integer.1≤N≤10^10

题意：给定一个N，输出1~N之间不能表示为a的b次方的数字个数。

思路：题目要求b>=2，因此可以遍历2~√N的每一个a，这样10^10的数量级会下降一半。进行遍历时，为了减少重复操作，对于某个n，如果已经被a1访问过，那么就不会被a2再访问，易知a1|a2。

code：

#include <bits/stdc++.h>
using namespace std;
#define inf 1e5+10
#define ll long long
const int gm=10010;
ll n;
int main()
{
    vector<bool> flag(1e5+5);//只需要对根号n以下的记录是否访问过
    cin>>n;
    ll ans=n;//初始ans为n
    for (ll i=2;i*i<=n;i++)
    {
        if (flag[i]==1)//如果该数之前被访问，就跳过
            continue;
        ll temp=i*i;//从平方开始累乘
        while (temp<=n)
        {
            ans--;//temp可以被表示，ans--
            if (temp<flag.size())//这个不能漏，大于sqrt(n)的数不需要再记录，不然vector规模太大
                flag[temp]=1;
            temp*=i;
        }
    }  
    cout<<ans<<endl;
    system("pause");
    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