HDOJ 5902 GCD is Funny
传送门：http://acm.hdu.edu.cn/showproblem.php?pid=5902
题目翻译
Alex发明了一个有趣的游戏. 一开始他在黑板上写了nn个正整数, 然后他开始重复进行如下的操作:
- 他选择黑板上三个数字a, b和c, 把他们从黑板上擦掉.
- 他从这三个数a, b和c中选择了两个数, 并计算出他们的最大公约数, 记这个数为d (d 可以是\(\gcd(a,b)\), \(\gcd(a,c)\)或者\(\gcd(b, c)\)).
- 他在黑板上写下两次数字d.
显然, 在操作(n-2)次后, 黑板上只会留下两个相同的数字. Alex想要知道哪些数字可以最终可能留在黑板上.
题解
在第一次选择3个数字(a,b,c)的时候，我们一定会扔掉一个数字，然后放入两个相同的数字GCD(a,b)。接下来的每次数字选择，我们都可以选择扔掉之前产生的有重复的数字，也可以扔掉之前从未使用过的数字。
所以，这样一看，最后可能留在黑板上的数字一定是原来留在黑板上的N个数字中，其中 2 ~ n-1 个数字的GCD。所以我们只需要循环把他们算出来即可。
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
//while(true) RP++; #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define LL long long using namespace std; const int Maxn=500; const int Maxm=1000; int n; int num[Maxn+5]; bool ans[Maxm+5]; int gcd(int a,int b){if (b==0) return a; else return gcd(b,a%b);} inline void solve(int T){ memset(ans,false,sizeof(ans)); scanf("%d",&n); for (int i=1;i<=n;i++) scanf("%d",&num[i]); for (int i=1;i<=n;i++) for (int j=i+1;j<=n;j++) ans[gcd(num[i],num[j])]=true; bool isNew=true; for (int Rt=1;Rt<=n-3 && isNew;Rt++){ isNew=false; for (int i=1;i<=1000;i++) if (ans[i]){ for (int j=1;j<=n;j++){ int ret=gcd(i,num[j]); if (ans[ret]==false){ ans[ret]=true; isNew=true; } } } } isNew=true; for (int i=1;i<=1000;i++) if (ans[i]){ if (!isNew) printf(" "); printf("%d",i); isNew=false; } printf("\n"); } int main(){ int T=0; while(scanf("%d",&T)!=EOF) for (int i=1;i<=T;i++) solve(i); return 0; } |
原文链接：HDOJ 5902 GCD is Funny
WNJXYKの博客 版权所有，转载请注明出处。
还没有任何评论，你来说两句吧!