【数论法求一堆数的最小公倍数,结果高达几千位】LOJ 1024 Eid_C/C++_编程开发_程序员俱乐部

中国优秀的程序员网站程序员频道CXYCLUB技术地图
热搜:
更多>>
 
您所在的位置: 程序员俱乐部 > 编程开发 > C/C++ > 【数论法求一堆数的最小公倍数,结果高达几千位】LOJ 1024 Eid

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

 2012/2/14 10:21:36  基德KID.1412  程序员俱乐部  我要评论(0)
  • 摘要:KIDx的解题报告题意:求n个数的最小公倍数,结果很大,得用高精度题目链接:http://lightoj.com/volume_showproblem.php?problem=1024找出每个数的素因子p,p必为最小公倍数的因子,最小公倍数中p的个数就是每个数的p的个数的最大值,最后,最小公倍数的因子及其个数都知道了,用高精度乘起来就是结果了,我这里用的是10000进制计算#include<iostream>#include<fstream>#include<
  • 标签:结果

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;
}

??

发表评论
用户名: 匿名