【推导】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;

}

巴特西

【推导】zoj3846 GCD Reduce

最新文章

热门文章