lightoj 1024 （高精度乘单精度）

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

题意：给你一些数，求它们的最小公倍数，结果可能会很大。

统计出每个素因子出现的最大次数，把他们相乘即可，需要高精度。

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int MAXN = 100010;
int ans[MAXN], cnt[MAXN], len;
void multiply(int fact){ //高精度乘单精度;
for(int i = 0;i < len;i ++) ans[i] *= fact;
for(int i = 0;i < len;i ++){
ans[i+1] += ans[i]/10;
ans[i] %= 10;
}
int tmp = ans[len];
while(tmp){
ans[len++] = tmp%10;
tmp /= 10;
}
}
int main(){
int t, CASE(0), n, tmp;
scanf("%d", &t);
while(t--){
scanf("%d", &n);
memset(cnt, 0, sizeof cnt);
memset(ans, 0, sizeof ans);
for(int i = 0;i < n;i ++){
scanf("%d", &tmp);
int fact = 2;
while(tmp != 1){
int num = 0;
while(tmp % fact == 0) num ++, tmp /= fact;
cnt[fact] = max(cnt[fact], num);
fact++;
}
}
ans[0] = len = 1;
for(int i = 2;i <= 10000;i ++) if(cnt[i]) multiply(pow(i, cnt[i]));
printf("Case %d: ", ++CASE);
for(int i = len - 1;i > 0;i --) printf("%d", ans[i]);
printf("%d\n", ans[0]);
}
return 0;
}