Description
You are given a sequence {A1, A2, ..., AN}. 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):
You do not need to minimize the number of used operations. However, you need to make sure that there are at most 5N operations.
Input
Input will consist of multiple test cases.
The first line of each case contains one integer N (1 ≤ N ≤ 105), indicating the length of the sequence. The second line contains Nintegers, A1, A2, ..., AN (1 ≤ Ai ≤ 109).
Output
For each test case, print a line containing the test case number (beginning with 1) followed by one integer M, indicating the number of operations needed. You must assure that M is no larger than 5N. If you cannot find a solution, make M equal to -1 and ignore the following output.
In the next M lines, each contains two integers i and j (1 ≤ i < j ≤ N), 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个数，然后对这n个数进行如下两步操作：
1.选取两个下标为i和j的数(i<j)
2.将两个数替换为他们的最大公约数。
选取一种你认为可行的方案，使最后的所有数都变成1，且操作数不超过5*n
思路：1和所有数的最大公约数都为1，所以只要该n个数中出现为1的数则可行，我的做法是从第一个数开始与后面的每个数取最大公约数，如果有1的话重复两次该操作就可以讲所有的数都变成1，不成功的情况其实只看最后一位n就可以，如果一次遍历后n可以为1那么可行，否则输出-1.注意输出格式两组测试数据之间有空行
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <sstream>
#include <algorithm>
#include <set>
#include <queue>
#include <stack>
#include <map>
using namespace std;
typedef long long LL;
LL n,mod;
int str[300010];
int gcd(int a,int b)
{
if(a<b)
swap(a,b);
while(b!=0) {
int r=b;
b=a%b;
a=r;
}
return a;
}
int main()
{
int n,i;
int icase=0;
int res;
while(~scanf("%d",&n)) {
for(i=0; i<n; i++)
scanf("%d",&str[i]);
int res=str[0];
for(i=1; i<n; i++)
res=gcd(res,str[i]);
if(res!=1) {
printf("Case %d: -1\n",++icase);
puts("");
} else {
int cnt=2*(n-1);
printf("Case %d: %d\n",++icase,cnt);
for(i=2; i<=n; i++)
printf("1 %d\n",i);
for(i=2; i<=n; i++)
printf("1 %d\n",i);
puts("");
}
}
return 0;
}原文：http://blog.csdn.net/u013486414/article/details/44564429