Main idea of the title:

Here you are n n n points, each point has a point weight a i a_i ai​. Two points i , j i,j i. There is an edge between J if and only if g c d ( a i , a j ) ≠ 1 gcd(a_i,a_j)\neq 1 gcd(ai​,aj​)​=1. Find the number of cut points in the graph

Topic idea:

Obviously there is one n 2 n^2 n2 algorithm for drawing and running cut points. Consider optimizing drawing construction:

There is an edge between two points if and only if they have a common prime factor. So we pull out these qualitative factors as new points. Then, for each point weight, the prime factor is decomposed and connected with the prime factor it contains.

So we get a maximum 2 n 2n 2n points, n l o g n nlogn nlogn edge graph (n numbers can contain at most) n n n different qualitative factors (this is the most common case) n n The number of n is the first n n n prime numbers) A number can contain less than l o g n logn logn different qualitative factors, the most common is n n n is the front x x Accumulation of x prime numbers) Therefore, this greatly optimizes the complexity of drawing construction

A question: how to prove that the cut point of this graph will not be affected?

prove:

1. Consider cutting point x x Several connected blocks separated by x must not pass through x x x is connected.

Suppose that a point is taken from each of any two connected blocks i , j i,j i. J. there is obviously no edge directly connected between the two points So we can only prove that the new virtual point will not connect two points that are not directly connected by edges.

2. According to the rules of drawing construction, the subgraph of the new imaginary point and its connected point in the original graph is a complete graph Because they contain common quality factors
So I got the certificate.

Specific methods:

1. Screen out first 1 e 7 \sqrt{1e7} 1e7 To obtain the prime factor of each number Save it with vector Complexity: O ( n a i l n a i ) O(\frac{n\sqrt{a_i}}{ln{\sqrt{a_i}}}) O(lnai​ ​nai​ ​​)

2. Count how many quality factors need to be added, and count the penetration of each quality factor point

3. Edge building: first add all the required quality factors, and then connect the edges

4. Run targin to find the cutting point Special note: if there is a quality factor point y y The penetration of y is 1 That is, the whole sequence has only one number x x This prime factor appears in x y y y. Then you don't have to connect them.

Because in this case, when we run targin, we will x x The x-point is regarded as the cut point Because it will y y y is isolated, but this is not necessarily the case. Because we must remember y y y does not exist, it is our virtual point. If you just put y y If a point y is isolated, it cannot be regarded as a cut point

AC Code: (now is the time) r a n k 1 rank1 rank1)

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define pb push_back
#define vi vector<int>
#define vll vector<ll>
const int maxn = 3e5 + 5;
const int maxm = 3300;
const int mod = 1e9 + 7;
bool bk[maxm];
int p[maxm] , cnt;
int id[maxm * maxm];
void getp ()
{
    for (int i = 2 ; i < maxm ; i++){
        if (!bk[i]) p[++cnt] = i;
        for (int j = 1 ; j <= cnt && p[j] * i < maxm ; j++){
            bk[p[j] * i] = 1;
            if (i % p[j] == 0) break;
        }
    }
    return ;
}
int a[maxn];
vector<int> e[maxn] , f[maxn];
// targin finding strong connectivity
int dfn[maxn] , low[maxn] , tot , iscut[maxn];
void dfs (int u , int fa)
{
    dfn[u] = low[u] = ++tot;
    int s = 0;
    for (auto v : e[u]){
        if (v == fa) continue;
        if (!dfn[v]){
            s++;
            dfs(v , u);
            low[u] = min(low[u] , low[v]);
            if (low[v] >= dfn[u]) iscut[u] = true;
        }else {
            low[u] = min(low[u] , dfn[v]);
        }
    }
    // Special root node
    if (fa == 0 && s == 1) iscut[u] = false;
}
int main()
{
    ios::sync_with_stdio(false);
    int n; cin >> n;
    getp();
    int ans = 0;
    map<int,int> mp;
    for (int i = 1 ; i <= n ; i++){
        cin >> a[i];
        int g = a[i];
        for (int j = 1 ; p[j] * p[j] <= g ; j++){
            if (g % p[j] == 0){
                f[i].push_back(p[j]);
                mp[p[j]]++;
                while (g % p[j] == 0) g /= p[j];
            }
        }
        if (g != 1) f[i].push_back(g) , mp[g]++;
    }
    // Mapping
    int m = n;
    for (int i = 1 ; i <= n ; i++){
        for (auto v : f[i]){
            if (mp[v] == 1) continue;
            if (!id[v]) id[v] = ++m;
            e[i].push_back(id[v]);
            e[id[v]].push_back(i);
        }
    }
    for (int i = 1 ; i <= n ; i++) if (!dfn[i]) dfs(i , 0);
    for (int i = 1 ; i <= n ; i++) ans += iscut[i];
    cout << ans << endl;
    return 0;
}