本文共 1467 字，大约阅读时间需要 4 分钟。

1616 最小集合

A君有一个集合。

这个集合有个神奇的性质。 若X,Y属于该集合，那么X与Y的最大公因数也属于该集合。 但是他忘了这个集合中原先有哪些数字。 不过幸运的是，他记起了其中n个数字。 当然，或许会因为过度紧张，他记起来的数字可能会重复。 他想还原原先的集合。 他知道这是不可能的…… 现在他想知道的是，原先这个集合中至少存在多少数。

样例解释：

该集合中一定存在的是{1,2,3,4,6}

输入

第一行一个数n(1<=n<=100000)。

第二行n个数，ai(1<=ai<=1000000，1<=i<=n)。表示A君记起来的数字。 输入的数字可能重复。

输出

输出一行表示至少存在多少种不同的数字。

输入样例

5

1 3 4 6 6

输出样例

5

题解

该集合中一定存在输入的数字中若干数的最大公因数。

这个证明比较简单，例如我们有 a1, a2, …, an 这些数，那么 gcd(a1,a2) 一定存在该集合，然后 gcd(a1,a2,a3) 也一定存在该集合，依次类推。 所以我们对于每个数i，都求出在n个数中有多少数是它的倍数,记为 f(i) 。 然后观察 f(2× i), f(3× i), …, f(x× i), … 中是否存在一个数等于 f(i) ，若不存在，则i一定存在于该集合。

代码

#include 
   
    #include 
    
     #include 
     
      #define ll long longusing namespace std;const int maxn = 1e6 + 10;const int mod = 1e9 + 7;int a[maxn];int have[maxn];int sum[maxn];int main() {
       int n;    cin >> n;    int mx = 0;    for (int i = 1; i <= n; i++) {
           cin >> a[i];        mx = max(a[i], mx);        have[a[i]] = 1;    }    for (int i = 1; i <= mx; i++) {
           for (int j = i; j <= mx; j += i) {
               if (have[j]) {
                   sum[i]++;            }        }    }    int ans = 0;    for (int i = 1; i <= mx; i++) {
           if (sum[i] == 0) {
               continue;        }        int flag = 0;        for (int j = i + i; j <= mx; j += i) {
               if (sum[i] == sum[j]) {
                   flag = 1;                break;            }        }        if (!flag) {
               ans++;        }    }    cout << ans << endl;    return 0;}
     
    
   

转载地址：https://blog.csdn.net/weixin_43820352/article/details/113106574 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！