题目 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
解题思路:可以发现ai的范围较小，考虑用数组mark来标记当前这个数该不该出现。那么对于每个数i枚举i的倍数，设集合A={j|mark[i*j]=1},若gcd（A）= 1那么i必然存在。
代码:
#include
using namespace std;
const int maxn = 1e6 + 10;
int mark[maxn];
int gcd(int a,int b){
return b == 0? a : gcd(b,a%b);
}int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n,a,Max = 0;
cin>>n;
for(int i = 1;
i <= n;
++i){
cin>>a;
mark[a] = 1;
Max = max(Max,a);
}
for(int i = Max;
i >= 1;
--i)
if(mark[i] == 0){
int num = 0;
for(int j = 1;
j * i <= Max;
j += 1)
if(mark[i * j]){
num = gcd(j,num);
if(num == 1) break;
}
if(num == 1) mark[i] = 1;
}
int ans = 0;
for(int i = 1;
i <= Max;
++i) ans += mark[i];
cout< 【51nod1616 最小集合(gcd 思维)】
推荐阅读
- HDU 5528【2015长春现场赛 B】 Count a * b
- 类欧几里得算法|[类欧几里得算法 数论] BZOJ 2987 Earthquake
- [数论] Codeforces 819D R #421 D.Mister B and Astronomers & 516E R #292 E. Drazil and His Happy Friends
- 模板 poj2947 Widget Factory 高斯消元
- 【扩展欧几里得】练习题
- 扩展欧几里得【数论
- 数论|hdu 5322 Hope（分治+NTT）
- HDU 5528 Count a × b
- 线性同余方程组
- 数论|AtCoder Beginner Contest 156 C.Rally