January2015

http:acm.zju.edu.cnonlinejudgeshowProblem.do?problemCode3844第一个，n个数，每次操作最大数和最小数都变成他们的差值，最后

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3844

第一个，n个数，每次操作最大数和最小数都变成他们的差值，最后n个数相同时输出此时的值，暴力跑。

1 #include 2 int main(){ 3 int t,n,a[16]; 4 while(~scanf("%d", 7 for(int i=0;ihttp://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5440

第二个，n个数，每次操作可以任意选两个数把他们变成他们gcd的值。最后问几步能都变成1，且输出每步选的数的下标。方法：先求出n个数的gcd，如果不为1，输出-1.否则一定能变成全1.变的方法是，先用第一个依次和后面的操作，直至第一个数变成1，然后再用第一个数把剩下的非1的都变掉。

1 #include 2 #include 3 using namespace std; 4 const int M=1e5+10; 5 typedef pair pii; 6 int a[M]; 7 int gcd(int a,int b){ 8 return b?gcd(b,a%b):a; 9 }10 vector ans;11 int main(){12 int n;13 int cas=1;14 while(~scanf("%d",i<=n;i++){16 scanf("%d",17 }18 int now=a[1];19 for(int i=2;i1){24 puts("-1");25 puts("");26 continue;27 }28 ans.clear();29 for(int i=2;i<=n;i++){30 int now=gcd(a[1],a[i]);31 a[1]=a[i]=now;32 ans.push_back(make_pair(1,i));33 if(now==1) break;34 }35 for(int i=2;i<=n;i++){36 if(a[i]==1) continue;37 ans.push_back(make_pair(1,i));38 }39 int len=ans.size();40 printf("%d\n",len);41 for(int i=0;iend

matrix_2015_1 138 - ZOJ Monthly, January 2015