【lightoj-1024】Eid (高精度)
2024-10-21 03:49:57
【题意】
给定n个数,求这n个数的最小公倍数。
【题解】
最小公倍数当然不能按常规方法来求,因为最大的数将近是10000^1000级别的。然鹅最小公倍数怎么搞呢?
这里发现了一个规律:
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;
最后要用到高精度乘法。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int a[], b[];
void Mul(int b[], LL n)
{
int i;
for(i = ; i <= b[]; i++) b[i] *= n;
for(i = ; i <= b[]; i++) b[i+] += b[i] / , b[i] %= ;
while(b[i]) b[i+] += b[i] / , b[i] %= , i++, b[]++;
}
LL q_pow(int x, int y)
{
LL ans = ;
while(y)
{
if(y&) ans *= x;
x *= x;
y >>= ;
}
return ans;
}
int main()
{
int t, n, i, cas = , m;
cin>>t;
while(t--)
{
scanf("%d", &n);
memset(a, , sizeof(a));
int max1 = ;
while(n--)
{
scanf("%d", &m);
max1 = max(max1, m);
for(i = ; i <= m; i++)
{
int tep = ;
while(m % i == )
tep++, m /= i;
a[i] = max(a[i], tep);
}
}
memset(b, , sizeof b);
b[] = , b[] = ;
for(i = ; i <= max1; i++)
{
if(a[i] != )
Mul(b, q_pow(i, a[i]));
}
printf("Case %d: ", ++cas);
for(i = b[]; i >= ; i--)
printf("%d", b[i]);
cout<<endl;
}
return ;
}
最新文章
- TypeScript Generics(泛型)
- 关于context:component-scan配置中use-default-filters参数的作用
- 【openresty】获取post请求数据FormInputNginxModule模块
- 深入理解asp.net里的HttpModule机制
- 高并发访问mysql时的问题(一):库存超减
- 【Android开发坑系列】如何让Service尽可能存活
- hadoop错误org.apache.hadoop.yarn.exceptions.YarnException Unauthorized request to start container
- 刨根问底:对于 self = [super init] 的思考
- 你我公益模式系统APP开发
- saiku运行时报错max_length_for_sort_data 需要set higher
- 痞子衡嵌入式:飞思卡尔i.MX RT系列MCU启动那些事(13)- 从Serial(1-bit SPI) EEPROM/NOR恢复启动
- MyString
- [matlab] 21.灰色预测、线性回归分析模型与最小二乘回归 (转载)
- iOS:解决UITextView自适应高度粘贴大量文字导致显示不全的问题
- ServiceStack.Redis遇到的问题:ServiceStack.Redis.Generic.RedisTypedClient`1”的方法“get_Db”没有实现。
- 解决HighChart开发遇到的2个问题
- php优秀框架codeigniter学习系列——前言
- Android RoboGuice开源框架、Butter Knife开源框架浅析
- Arduino Leonardo读取DHT22温湿度传感器
- 多线程的学习与GDI的学习
热门文章
- 深拷贝与浅拷贝js,方法
- windows平台kettle连接hbase的问题
- JSON.stringify without quotes on properties?
- Linux Swap交换分区介绍
- 从toString()方法到Object.prototype.toString.call()方法
- 20145331 《Java程序设计》第2次实验报告
- C++第二次上机5-5
- c#结构体和字节流之间的相互转换
- 再也不学AJAX了!(三)跨域获取资源 ② - JSONP &; CORS
- Maven错误recv failed