数论——GCD

ZOJ Problem Set - 3846

题意：

给 N 个数，任取两个数Ai、Aj，求出这两数的GCD，然后用GCD替换这两个数的值。
直至这n个数的值都相等为止，此时输出求GCD的次数，然后按顺序输出每次求GCD的对应的那两个数。
若求GCD的次数超出5*N次时仍未满足停止条件则输出 -1

思路：

只要出现1，就可以将其余的数都变成1，所以，我们从第一个数开始，
GCD（Ai,Ai+1） ,i++;一旦满足GCD（Ai,Ai+1） == 1，便可停止，然后用Ai（或Ai+1）与其他的数做GCD。如此一来求GCD的次数最多不会超过2n-2次。
若i=n-1后仍未出现1，则说明所有数都不会化为相同的数。所以输出 -1

AC代码如下：

#include <iostream>
#include <cstring>
#include <algorithm>
#include "stdio.h"
#include<fstream>

using namespace std;
#define Max_N 100002
int N;
int num[Max_N];

int kgcd(int a, int b) {
    if (a == 0) return b;
    if (b == 0) return a;
    if (!(a & 1) && !(b & 1)) return kgcd(a>>1, b>>1) << 1;
    else if (!(b & 1)) return kgcd(a, b>>1);
    else if (!(a & 1)) return kgcd(a>>1, b);
    else return kgcd(abs(a - b), min(a, b));
}
int main() {
    int times = 0;
    while(scanf("%d",&N)!=EOF) {
        bool exist_one = false;

        int tag = 0;
        times++;
        for(int i =0 ; i<N; i++)
            scanf("%d",&num[i]);
        for(int i =0; i<N-1; i++) {
            int temp = kgcd(num[i],num[i+1]);
            if(temp ==1) {
                exist_one = true;
                tag = i+1;//取较小的那个数
                break;
            }
            num[i] = temp,num[i+1] = temp;
        }
        printf("Case %d: ",times);

        if(exist_one) {
            printf("%d\n",tag+N-2);
            for(int i = 1; i<=tag; i++)
                printf("%d %d\n",i ,i+1);
            for(int i = tag; i>1; i--)
                printf("%d %d\n",i-1 ,i);
            for(int i =tag+1; i<N; i++)
                printf("%d %d\n",i ,i+1);

        } else {
            printf("%d",-1);
            printf("\n");
        }
        printf("\n");
    }

}

如有错误，还望指出！
转载请注明出处：http://blog.csdn.net/Big_Heart_C