首页 > 代码库 > 1616 最小集合 51NOD（辗转相处求最大公约数+STL）
1616 最小集合 51NOD（辗转相处求最大公约数+STL）
1616 最小集合
基准时间限制：1 秒 空间限制：131072 KB 分值: 80 难度：5级算法题
收藏
关注A君有一个集合。
这个集合有个神奇的性质。
若X,Y属于该集合，那么X与Y的最大公因数也属于该集合。
但是他忘了这个集合中原先有哪些数字。
不过幸运的是，他记起了其中n个数字。
当然，或许会因为过度紧张，他记起来的数字可能会重复。
他想还原原先的集合。
他知道这是不可能的……
现在他想知道的是，原先这个集合中至少存在多少数。
样例解释：
该集合中一定存在的是{1,2,3,4,6}
Input
第一行一个数n(1<=n<=100000)。 第二行n个数，ai(1<=ai<=1000000，1<=i<=n)。表示A君记起来的数字。 输入的数字可能重复。
Output
输出一行表示至少存在多少种不同的数字。
Input示例
5 1 3 4 6 6
Output示例
5
#include<iostream> #include<cstdio> #include<cstring> #include<set> using namespace std; set<int>se; int n; int b[10000],ans; int gcd(int x,int y){ return x == 0 ? y: gcd(y % x, x); } int main(){ cin>>n; for(int i = 0; i < n; i++){ cin>>b[i]; se.insert(b[i]); } for(int i = 0; i < n; i++){ for(int j = i+1; j < n; j++){ se.insert(gcd( b[i] , b[j] )); } } cout<<se.size(); }
思路：输入数b，用STL中的set集合存储，因为set集合不含有相同的元素，所以实现了去重；
然后两两比较找GCD，存入集合se中，最后se的长度就是所存数子个数；
题目地址：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1616
1616 最小集合 51NOD（辗转相处求最大公约数+STL）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。