【推导】zoj3846 GCD Reduce

题意：给你n个正整数a1…an，一次操作是选择任意两个数ai,aj，将它们都替换成gcd(ai,aj)。让你在5n步内将所有数变为1。或者输出不可能。

如果所有数的gcd不为1，显然不可能。

否则从a1开始，一路和下一个数取上gcd，一定能在某个时刻，让a1这个数变成1。

然后就好办了，再让a2…an分别与a1取上gcd，就全变成1了。

不超过2n步。

#include<cstdio>
#include<algorithm>
using namespace std;
int n,a[100005];
int main(){
//freopen("g.in","r",stdin);
int zu=0;
while(scanf("%d",&n)!=EOF){
printf("Case %d: ",++zu);
for(int i=1;i<=n;++i){
scanf("%d",&a[i]);
}
int now=a[1],ans;
for(int i=2;i<=n;++i){
now=__gcd(now,a[i]);
if(now==1){
ans=i-1;
break;
}
}
if(now!=1){
puts("-1\n");
continue;
}
printf("%d\n",ans+n-1);
for(int i=2;i<=ans+1;++i){
printf("%d %d\n",1,i);
}
for(int i=2;i<=n;++i){
printf("1 %d\n",i);
}
puts("");
}
return 0;
}