zoj 3846 GCD Reduce（数论）

题目链接

GCD Reduce

---

Time Limit: 2 Seconds      Memory Limit: 65536 KB      Special Judge

---

You are given a sequence {A₁, A₂, ..., A_N}. 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 i and j (1 ≤ i < j ≤ N);
• change both A_i and A_j to gcd(A_i, A_j), where gcd(A_i, A_j) is the greatest common divisor of A_i and A_j.

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 ≤ 10⁵), indicating the length of the sequence. The second line contains N integers, A₁, A₂, ..., A_N (1 ≤ A_i ≤ 10⁹).

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个数。每次操作步骤如下：

1，选取两个数，设它们的下标为i，j。（i<j）

2，将两个数替换为它们的最大公约数。

输出一种操作方案，使得最后所有的数都变成一，且操作数不超过5*n。

题意：1与所有正数的最大公约数都为1。所以我们操作出1，然后用这个1把所有数都变成1就可以了。先操作（1,2），然后（2,3），然后（3,4）......直到（n-1，n），这时第n个数就是n个数的最大公约数，如果第n个数不为1则无解。否则，再用最后一个数与前（n-1）个数操作一次，就可以把所有数都变成1了。总操作数2n-2次。

代码如下：

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
#include<string>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<stdlib.h>
#include<vector>
#define inff 0x3fffffff
#define nn 110000
#define mod 1000000007
typedef long long LL;
const LL inf64=inff*(LL)inff;
using namespace std;
int n;
int a[nn];
vector<pair<int,int> >ans;
int gcd(int x,int y)
{
    if(y==0)
        return x;
    return gcd(y,x%y);
}
int main()
{
    int i;
    int cas=1;
    while(scanf("%d",&n)!=EOF)
    {
        ans.clear();
        for(i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
        }
        int ix=a[1];
        int id=1;
        if(ix!=1)
        {
            for(i=2;i<=n;i++)
            {
                ix=gcd(ix,a[i]);
                ans.push_back(make_pair(i-1,i));
                if(ix==1)
                {
                    id=i;
                    break;
                }
            }
        }
        printf("Case %d: ",cas++);
        if(ix!=1)
        {
            puts("-1");
        }
        else
        {
            for(i=1;i<=n;i++)
            {
                if(i==id)
                    continue;
                if(i<id)
                    ans.push_back(make_pair(i,id));
                else
                    ans.push_back(make_pair(id,i));
            }
            int la=ans.size();
            printf("%d\n",la);
            for(i=0;i<la;i++)
            {
                printf("%d %d\n",ans[i].first,ans[i].second);
            }
        }
        puts("");
    }
    return 0;
}