题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5902 转载链接:http://blog.csdn.net/xtulollipop/article/details/52664876
题意:
个人感想: 当时BC的时候我一看到题目想都不想 就直接用n^2的跑一遍两个数得gcd就是答案了… 当场交直接AC,玛德智障,原来出题人标程都搞错,以为是个水题,却并不然,那一场BC GG了好多人,看题3分钟啊真是… 不过赛过我知道了真正题意之后死活也想不出该怎么做,我想着该在性质上入手,但是我就是想到n2跑一遍,然后面取数gcd那一块,我想得太复杂了…然后非常凌乱,然后就没整理好思维,最后我还是只能借助题解了… 我现在才感觉自己真尼玛弱鸡… 我觉得我以后得把公式写好在草稿纸上,其实那时候乱想的时候我已经写到全部公式了,就是深究不下去,可能就是对这个感觉不太好,没那感觉啊gcd. 假设有n个数 a b c d e f g h. 那么我们知道 作者做法是 gcd(a,b,c)=t 然后n个数就变成 t t d e f g h 我们肯定知道 t必定是可以保留下来的.我们需要更多的其他gcd. 那么既然要做多个数 那个肯定是 通过 gcd(t,d or e or f or g or h)=x;来获取新的gcd. 直接把那个 保留的t 抛弃掉就行了. 所以还得做 必须对n个数做 n-3次循环在原数组中找. t t d) e) f) g) h).
ps:那时候我为什么想不出来呢,就是我觉得 对于 t t d e f g h 来说,可能通过 gcd（f,g,h）=x 得到的 t t d e f x x 然后保留gcd(t,x)=z 其实通过刚刚这样枚举一样可以枚举出这样的结果 先做 gcd（t,f）=m 再做 gcd（m,g）=n 再做 gcd（n,j）=z 必然等于gcd(t,gcd(f,g,h))=z;
说明一下 gcd(a,b,c)=k:代表的是能再3个数中选2个抛弃1个得到的约数为k 所以这样就可以得到答案啊,我觉得我又得爆刷一个专题了。。 求大牛带飞…实在没感觉…
分析:数论+思维
代码:
/* Author:GavinjouElephant * Title: * Number: * main meanning： * * * */ #include <iostream> using namespace std; #include <cstdio> #include <cmath> #include <cstring> #include <algorithm> #include <sstream> #include <cctype> #include <vector> #include <set> #include <cstdlib> #include <map> #include <queue> //#include<initializer_list> //#include <windows.h> //#include <fstream> //#include <conio.h> #define MaxN 0x7fffffff #define MinN -0x7fffffff #define lson 2*k #define rson 2*k+1 typedef long long ll; const int INF=0x3f3f3f3f; const int maxn=1e3+10; int Scan()//读入整数外挂. { int res = 0, ch, flag = 0; if((ch = getchar()) == '-') //判断正负 flag = 1; else if(ch >= '0' && ch <= '9') //得到完整的数 res = ch - '0'; while((ch = getchar()) >= '0' && ch <= '9' ) res = res * 10 + ch - '0'; return flag ? -res : res; } void Out(int a) //输出外挂 { if(a>9) Out(a/10); putchar(a%10+'0'); } int T; int n; int a[maxn]; bool g[maxn]; int gcd(int a,int b) { if(b==0)return a; return gcd(b,a%b); } int main() { #ifndef ONLINE_JUDGE freopen("coco.txt","r",stdin); freopen("lala.txt","w",stdout); #endif scanf("%d",&T); while(T--) { memset(g,0,sizeof(g)); scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); } for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { if(i==j)continue; g[gcd(a[i],a[j])]=true; } } int cnt=n-3; bool flag=true; for(int i=1;i<=cnt&&flag;i++) { flag=false; for(int j=1;j<=1000;j++) { if(g[j]) { for(int k=1;k<=n;k++) { int t=gcd(j,a[k]); if(!g[t]) { flag=true; g[t]=true; } } } } } flag=true; for(int i=1;i<=1000;i++) { if(g[i]) { if(flag){printf("%d",i);flag=false;} else printf(" %d",i); } } cout<<endl; } return 0; }