首页 > 代码库 > LightOj1024 - Eid (求n个数的最小公约数+高精度)
LightOj1024 - Eid (求n个数的最小公约数+高精度)
题目链接：http://lightoj.com/volume_showproblem.php?problem=1024
题意：给你n(2<=n<=1000)个数, 然后求n个数的最小公倍数，每个数的大小是1---10000;所以答案会很大，可能达到1000个4位数相乘；所以结果很大，将近4000位;
所以一定会涉及到高精度运算；同时我们也不能直接循环求最小公倍数；我们可以把一个数分解成多个质数相乘，然后找到所有数中，出现的质数最多的那个对应的次方，然后再把结果乘起来即可;
例如样例
4
5 6 30 60
5 : 5 //说明最小公倍数的因子中一定有一个5
6 : 2*3 //说明最小公倍数的因子中一定有一个2和一个3;
30 : 2*3*5 //说明最小公倍数的因子中一定有一个2和一个3和一个5;
60 : 2^2*3*5 //说明最小公倍数的因子中一定有2个2和一个3和一个5;
所以我们可以忽略那些个数比较少的， 找到说明结果中一定含有 2个2 1个3 1个5;
需要注意的是，因为每次进行大整数相乘时都是用的N，以至于TLE了无数次，所以可以用多位一起输出的方法进行;
#include <stdio.h>#include <string.h>#include <algorithm>#include <math.h>typedef long long LL;#define N 10001using namespace std;const double eps = 1e-6;int f[101], p[101], k = 0;void Prime(){ for(int i=2; i<101; i++) { if(!f[i])p[k++] = i; for(int j=i; j<101; j+=i) f[j] = 1; }}int ans[1001], cnt[N];void Mul(int a[], int num){ for(int i=0; i<1000; i++) a[i] = a[i]*num; for(int i=0; i<1000; i++) { a[i+1] += a[i]/10000; a[i] = a[i]%10000; }}void PUTS(int a[]){ int i=1000; while(i>=0 && a[i]==0) i--; printf("%d", a[i--]); while(i>=0) printf("%04d", a[i--]); printf("\n");}int main(){ Prime(); int n, T, t = 1; scanf("%d", &T); while(T--) { memset(cnt, 0, sizeof(cnt)); memset(ans, 0, sizeof(ans)); int num; scanf("%d", &n); for(int i=1; i<=n; i++) { scanf("%d", &num); for(int j=0; j<k && p[j]*p[j] <= num; j++) { int s = 0; while(num%p[j] == 0) { s ++; num /= p[j]; } cnt[p[j]] = max(cnt[p[j]], s); } if(num > 1) cnt[num] = max(cnt[num], 1); } ans[0] = 1; for(int i=0; i<N; i++) { if(!cnt[i]) continue; int ret = 1; for(int j=0; j<cnt[i]; j++) ret *= i; Mul(ans, ret); } printf("Case %d: ", t++); PUTS(ans); } return 0;}
LightOj1024 - Eid (求n个数的最小公约数+高精度)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。