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