【数论法求一堆数的最小公倍数，结果高达几千位】LOJ 1024 Eid

KIDx的解题报告

题意：求n个数的最小公倍数，结果很大，得用高精度

 

题目链接：http://lightoj.com/volume_showproblem.php?problem=1024

 

找出每个数的素因子p，p必为最小公倍数的因子，最小公倍数中p的个数就是每个数的p的个数的最大值，最后，最小公倍数的因子及其个数都知道了，用高精度乘起来就是结果了，我这里用的是10000进制计算

 

 

#include <iostream>
#include <fstream>
#include <algorithm>
#include <string>
#include <set>
//#include <map>
#include <queue>
#include <utility>
#include <iomanip>
#include <stack>
#include <list>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <ctype.h>
using namespace std;
#define M 1305

int res[M], p[M], cnt[10005], fac[M];
bool hash[10005];

int main ()
{
	int i, j, t, n, k = 0, x, w, cc = 1, m;
	/*****************素数打表*****************/
	for (i = 2; i < 10001; i++)
	{
		if (!hash[i])
		{
			p[k++] = i;
			for (j = i << 1; j < 10001; j+=i)
				if (!hash[j])
					hash[j] = true;
		}
	}
	/*****************素数打表*****************/
	scanf ("%d", &t);
	while (t--)
	{
		scanf ("%d", &n);
		memset (cnt, 0, sizeof(cnt));
		int id = 0;
		while (n--)
		{
			scanf ("%d", &x);
			for (i = 0; i < k && p[i] <= x; i++)
			{
				int tp = 0;
				while (x % p[i] == 0)
					tp++, x /= p[i];
				if (tp > cnt[p[i]])
				{
					if (cnt[p[i]] == 0) fac[id++] = p[i];//记录最小公倍数中的素因子
					cnt[p[i]] = tp;		//记录素因子p[i]的最大个数
				}
			}
		}
		m = 1;		//初始时res的位数
		w = 0;		//进位
		memset (res, 0, sizeof(res));
		res[0] = 1;	//初始时res是1
		for (i = 0; i < id; i++)
		{
			for (j = 0; j < cnt[fac[i]]; j++)
			{	//最小公倍数中一共有cnt[fac[i]]个fac[i]因子，所以要乘cnt[fac[i]]次
				for (x = 0; x < m; x++)		//按位相乘
				{
					res[x] = res[x] * fac[i] + w;
					w = 0;		//进位用过以后记得清0
					if (res[x] >= 10000)
						w = res[x] / 10000, res[x] %= 10000;
				}
				while (w > 0)
					res[m++] = w % 10000, w /= 10000;
			}
		}
		printf ("Case %d: %d", cc++, res[m-1]);
		//因为是第一个数，不用补足4位，因为不能有前导0
		for (i = m - 2; i >= 0; i--)
			printf ("%04d", res[i]);
		//用的一万进制，中间部分的数要补足4位
		printf ("\n");
	}
	return 0;
}