K. Lonely Numbers

图片说明

题意

给定1-n，问里面有多少个孤独的数，如果一个数a，b可以使得a,a/gcd(a,b),b/gcd(a,b)构成三角形，a，b就不会孤独。

解法

对于非平方数的合数x，必定有一个因子是小于,令其为y，则
的gcd为y，三角形就变成了 ,其中, 因为
所以就能构成合法的三角形，y + z-1>=Z 而这里的y*(z-1) 和 z都是合数，所以是合数就不是孤独的

对于质数x，只有他的 出现才可以，构成这样的三角形

#include <bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug_in  freopen("in.txt","r",stdin)
#define debug_out freopen("out.txt","w",stdout);
#define pb push_back
#define all(x) x.begin(),x.end()
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const int maxn = 1e6+10;
const int maxM = 1e6+10;
const int inf = 1e8;
const ll inf2 = 1e17;

template<class T>void read(T &x){
    T s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    x = s*w;
}
template<class H, class... T> void read(H& h, T&... t) {
    read(h);
    read(t...);
}
template <typename ... T>
void DummyWrapper(T... t){}

template <class T>
T unpacker(const T& t){
    cout<<' '<<t;
    return t;
}
template <typename T, typename... Args>
void pt(const T& t, const Args& ... data){
    cout << t;
    DummyWrapper(unpacker(data)...);
    cout << '\n';
}


//--------------------------------------------
int T,N;
bool vis[maxn];
int P[maxn],tail;
int ans[maxn];
void init(int N){
    for(int i = 2;i<=N;i++){
        if(!vis[i]) P[tail++] = i;
        for(int j = 0;j<tail && P[j] <= N/i;j++){
            vis[P[j] * i] = 1;
            if(i%P[j] == 0) break;
        }
    }

    for(int i = 1;i<=N;i++){ //预处理所有的答案
        ans[i] += ans[i-1];
        if(!vis[i]) ans[i]++;
        int ok = 0;
        int x = sqrt(i);
        if(x * x == i && x != 1){
            if(!vis[i]) ans[i]--,vis[i] = 0;
            if(!vis[x]) ans[i]--,vis[x] = 0;
        }
    }
}

int main(){
    // debug_in;

    read(T);
    init(1000000);
    while(T--){
        read(N);
        printf("%d\n",ans[N]);
    }

    return 0;
}