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

基德KID.1412

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