李大仁博客

/*<!--HTML */
/*
*author CG , lidaren.com
*DEBUG GCC,TC
*/
#include"stdio.h"
#include"math.h"
#include"conio.h"
#define MAX 20
/*MAX为最大输入20*/
/*时间复杂度 O(n) 空间复杂度 O(n)*/
int main()
{
 int a[MAX] , result , i;
 int trim (long *num);
 int function (int a[] , int len);
 clrscr();
 /*输入整数 输入 1 结束*/
 for(i = 0 ; i < MAX ; i++)
 {
  scanf("%d" , a[i]);
  if(a[i] == 1)
   break;
 }/*for*/
 result = max_common_divisor(a , i - 1);
 printf("%d" , result);
 getch();
 return 0;
}/*main*/
 
/*trim 清理数尾0 相当于带进位循环右移*/
int trim(long *num)
{
 int count = 0;
 while((*num) % 2 == 0)
 {
  (*num) /= 2;
  count++;
 }/*while*/
 return count;
}/*trim*/
 
/*max_common_divisor求最大公约数*/
int max_common_divisor(int a[] , int len)
{
 int zero , tz , ws , i;
  /*zero 数尾0的个数
  tz 临时计数 记录num的zero数
  ws 最终公约数有效数位的位数*/
 long num, base = a[0];
  /*num 临时存放所要求的数
  base 公约数的有效基数*/
 if(len == 0)  return 0;
  /*如果长度为0返回0*/
 zero = trim(base);
 for(i = 1 ; i <= len ; i++)
 {
  num = a[i];
  if(num < 0) num = -num;
   /*置反*/
  else if(num == 0) return 0;
   /*num为0 返回 0*/
  tz = trim( &#038;num);
  if(tz < zero) zero = tz;
   /*置换zero*/
  if(num == base) continue;
   /*有效数位相同*/
  num ^= base;
   /*num异或base 求出相同数位结尾 10 11101^00 01101=101 0000 ,0000可以被trim()处理*/
  ws = trim( &#038;num);
  base &#038;= (long) pow(2 , ws)-1;
   /*base截取尾部有效数位 1011101 截取5位 就是1011101 &#038; 00011111 得11101*/
 }/*for*/
 return base <<zero;
  /*base右移后返回*/
}/*max_common_divisor*/
 
/*-->*/