Subtask 1

Với subtask này, ta sẽ xét từng số từ 1 đến ~N~ có phải là dạng của đề bài hay không rồi đếm. Sử dụng thuật toán phân tích thành thừa số nguyên tố trong ~O(\sqrt N)~ không đủ nhanh cho bài này. Nên, ta phải sử dụng sàng ước cho bài này.

Độ phức tạp: ~O(N\log N)~

Subtask 2

Nhận xét: ~p^3*q^3 \le N \le 10^{18}~. Hay, ~p*q \le 10^6~. Vì thế, bài toán trở thành đến số lượng số có đúng 2 ước nguyên tố và chúng phân biệt. Ta cũng có thể giải bài này với sàng ước.

Độ phức tạp: ~O(\sqrt[3]{N} \log \sqrt[3]{N})~

Code mẫu

#include<bits/stdc++.h>
#define ll long long
#define ntr "\n"
#define mod (ll)(1e9+7)
#define taskname ""
#define frep freopen(taskname".inp","r",stdin); freopen(taskname".out","w",stdout);
using namespace std;
ll sieve[1000001];
void fills(){
    for(int i=1;i<=1e6;i++) sieve[i]=i;
    for(int i=2;i<=1e6;i++){
        if(sieve[i]==i){
            for(int j=2*i;j<=1e6;j+=i){
                sieve[j]=min(sieve[j],i*1LL);
            }
        }
    }
}
bool check(ll a){
    set<ll> s;
    ll v=a;
    while(a!=1){
        s.insert(sieve[a]);
        a/=sieve[a];
    }
    if(s.size()!=2) return false;
    ll c=1;
    for(auto i:s) c*=i;
    return c==v;
}
int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    //frep;
    fills();
    ll n;
    cin>>n;
    ll cnt=0;
    for(ll i=2;i*i*i<=n;i++){
        cnt+=check(i);
    }
    cout<<cnt;
}