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