算法竞赛--最大公约数与最小公倍数

辗转相除法求最大公约数

int gcd(int a,int b)
{
	if(b==0)
		return a;
	else
		return gcd(b,a%b);

}

1.最大公约数

输入两个正整数，求其最大公约数。

输入:

测试数据有多组，每组输入两个正整数。

输出:

对于每组输入,请输出其最大公约数。

样例输入:

49 14

样例输出:

参考代码如下:

#include <stdio.h>
int gcd(int a,int b)
{
	if(b==0)
		return a;
	else
		return gcd(b,a%b);
}
int main()
{
	int a,b;
	while(scanf("%d%d",&a,&b)!=EOF)
		printf("%d\n",gcd(a,b));
	return 0;
}

2.Least Common Multiple

The least common multiple (LCM) of a set of positive integers is the smallest positive integer which is divisible by all the numbers in the set. For example, the LCM of 5, 7 and 15 is 105.

input：

Input will consist of multiple problem instances. The first line of the input will contain a single integer indicating the number of problem instances. Each instance will consist of a single line of the form m n1 n2 n3 … nm where m is the number of integers in the set and n1 … nm are the integers. All integers will be positive and lie within the range of a 32-bit integer.

output：

For each problem instance, output a single line containing the corresponding LCM. All results will lie in the range of a 32-bit integer.

Sample input：

1
2
3

2
2 3 5
3 4 6 12

Sample output:

1
2

15
12

思路:用数组存储数值，每两个求最大公约数

参考代码如下:

#include<stdio.h>
int gcd(int a,int b)
{
	if(b==0)
		return a;
	else
		return gcd(b,a%b);
}
int main()
{
	int n,a[105];
	while(scanf("%d",&n)==1)
	{
		while(n--)
		{
			int m;
			scanf("%d",&m);
			for(int i=0;i<m;i++)
				scanf("%d",&a[i]);//存储要求最小公倍数的值
			for(int i=0;i<m-1;i++)
			{
				int temp=gcd(a[i],a[i+1]);
				a[i+1]=a[i]/temp*a[i+1];///计算最小公倍数
			}
			printf("%d\n",a[m-1]);
		}
	}
	return 0;
}