GCD Reduce
Time Limit: 2 Seconds Memory Limit: 65536 KB Special Judge
You are given a sequence {, , ..., }. You task is to change all the element of the sequence to 1 with the following operations (you may need to apply it multiple times):
- choose two indexes and (1 ≤ < ≤ );
- change both and to gcd(, ), where gcd(, ) is the greatest common divisor of and .
You do not need to minimize the number of used operations. However, you need to make sure that there are at most 5 operations.
Input
Input will consist of multiple test cases.
The first line of each case contains one integer (1 ≤ ≤ 10), indicating the length of the sequence. The second line contains integers, , , ..., (1 ≤ ≤ 10).
Output
For each test case, print a line containing the test case number (beginning with 1) followed by one integer , indicating the number of operations needed. You must assure that is no larger than 5. If you cannot find a solution, make equal to -1 and ignore the following output.
In the next lines, each contains two integers and (1 ≤ < ≤ ), indicating an operation, separated by one space.
If there are multiple answers, you can print any of them.
Remember to print a blank line after each case. But extra spaces and blank lines are not allowed.
Sample Input
4
2 2 3 4
4
2 2 2 2
Sample Output
Case 1: 3
1 3
1 2
1 4 Case 2: -1
题意：给你N个数，每次任意选取两个数，然后这两个数的值会变成gcd(a,b)，如果能把整个序列都变成1的话，求选择的顺序；
思路：很明显只要做出1就行了，gcd(1,x)=1,我从第一个数开始一直向后面去gcd，取到第i个数肯定就是那么1的值前i个数的gcd，只要判断一直取到最后一个第1个数有没有变成1就行了，判断有之后，说明除了第一个数其他的n-1个数肯定会是有一个数跟第一个数的gcd为1，反证法就能很好的证明，那么只要第一个数跟另外的n－1个数依次取gcd，碰到互质就跳出来，并记录点，那么只要先选择1和这个点，剩下的n－2个数直接和1取就行了，但是这样交上去时wa的。。。你第一个数依次和后面的数取gcd那么取到最后一个的时候，1这个数肯定是前n个数的最大公约数，如果第一个数此时为1的话，那么再进行一次操作就好了，要求操作次数小于5＊n，这个时候只是2*（n－1），完全是可以的，这样交上去是对的，反过来想，第一个数取到最后为1，那么最后一个数肯定这个时候也为1啊，我从后面往前GCD肯定也是对的，但是这样写的话交上去也是wa的，应该是special judge没有写好。。。
#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;
#define N 100100
int a[N];
int gcd(int a,int b)
{
if(b==) return a;
return gcd(b,a%b);
}
int main()
{
int n;
int cnt=;
while(scanf("%d",&n)!=EOF)
{
cnt++;
for(int i=;i<=n;i++)
scanf("%d",&a[i]);
int res=a[];
for(int i=;i<=n;i++)
res=gcd(res,a[i]);
if(res!=)
printf("Case %d: -1\n\n",cnt);
else
{
printf("Case %d: %d\n",cnt,*(n-));
for(int i=;i<=n;i++)
printf("1 %d\n",i);
for(int i=;i<=n;i++)
printf("1 %d\n",i);
printf("\n");
}
}
return ;
}