D. Not Adding

传送门：CF

正文：

这道题是一道数论题，有两种解法，都挺有趣的。

解法一：

#include<bits/stdc++.h>
#define maxn 1000005
using namespace std;
int a[maxn];
bool vis[maxn];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n,ans=0; cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i],vis[a[i]]=1;
	for(int i=1;i<=1e6;i++)
	{
		if(vis[i]) continue;
		int p=-1;
		for(int j=2*i;j<=1e6;j+=i)
		{
			if(!vis[j]) continue;
			if(p==-1) p=j/i;
			else
			{
				p=__gcd(p,j/i);
				if(p==1) {ans++,vis[j]=1; break;}
			}
		}
	}
	cout<<ans;
	return 0;
}

这里用了一个性质：若干个数只要有两个数是互质的，则

我们要判断  可以不可以通过更大的数得到，就要看存不存在两个数，满足

解法二：（代码取自jiangly）

#include <bits/stdc++.h>

using i64 = long long;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n;
    std::cin >> n;
    
    int m = 0;
    std::vector<int> a(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
        m = std::max(m, a[i]);
    }
    
    std::vector<int> f(m + 1);
    for (auto x : a) {
        f[x]++;
    }
    for (int i = 1; i <= m; i++) {
        for (int j = 2 * i; j <= m; j += i) {
            f[i] += f[j];
        }
    }
    
    int ans = 0;
    for (int i = 1; i <= m; i++) {
        bool nice = f[i] > 0;
        for (int j = 2 * i; j <= m; j += i) {
            if (f[i] == f[j]) {
                nice = false;
            }
        }
        ans += nice;
    }
    
    std::cout << ans - n << "\n";
    
    return 0;
}