Home > 算法研究 > 求输入的N(1~20)个整数(1~200000)的最大公约数算法

求输入的N(1~20)个整数(1~200000)的最大公约数算法

求输入的N(1~20)个整数(1~200000)的最大公约数算法
盐城师范学院软件协会 ACM/ICPC 试题
如需转载请保留相关作者注释,标明出处
说明:
算法使用了位运算的优化,减少MOD运算和除法运算的开销
实现一次遍历求出结果
算法时间复杂度O(n),最差情况O(Log2^C *N)C=所有数中最大数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
/*<!--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*/
 
/*-->*/
Categories: 算法研究 Tags: , ,
  1. blocks
    October 17th, 2009 at 22:48 | #1

    展示代码的那个什么玩意儿是不是有问题?#038;这个都弄进去了……

  2. October 18th, 2009 at 08:51 | #2

    貌似是HTML字符编码的问题,多谢指正

  1. No trackbacks yet.