ATcoder E - Flatten 质因子分解求LCM
2024-08-28 01:07:05
题解:其实就是求n个数的lcm,由于数据特别大,求lcm时只能用质因子分解的方法来求。
质因子分解求lcm。对n个数每个数都进行质因子分解,然后用一个数组记录某个质因子出现的最大次数。然后累乘pow(x,cnt),即质因子x出现了cnt次。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1E6+;
const ll mod=1e9+;
ll arr[N];
ll mp[N];
ll ksm(ll a,ll b){
ll res=;
while(b){
if(b&) res=res*a%mod;
a=a*a%mod;
b>>=;
}
return res%mod;
}
int main()
{
ios::sync_with_stdio(false );
ll n;
cin>>n;
ll mx=;
for(ll i=;i<=n;i++){
cin>>arr[i];
mx=max(mx,arr[i]);
}
ll pos=;
for(ll i=;i<=n;i++){
ll x=arr[i];
ll y=sqrt(x);
for(ll j=;j<=y;j++){
ll cnt=;
while(x%j==){
x/=j;
cnt++;
}
mp[j]=max(mp[j],cnt);
}
if(x!=) mp[x]=max(mp[x],(ll));
}
ll sum=;
for(ll i=;i<=mx;i++)
sum=(sum%mod*ksm(i,mp[i])%mod)%mod;
ll ans=;
for(ll i=;i<=n;i++){
ans+=sum*ksm(arr[i],mod-)%mod;
}
cout<<ans%mod<<endl;
return ;
}
最新文章
- 【JavaScript】javascript 方法 test()
- Homebrew安装及使用
- windows磁盘分区
- css3创建一个上下线性渐变色背景的div
- grep、egrep、fgrep
- [Java Web – 3A] – Spring MVC开发注意事项
- android 访问SMS短信收件箱
- javascript中的简单三角函数
- 语音信号处理之(三)矢量量化(Vector Quantization)
- 802.11(wifi)的MAC层功能
- Express4.x动态的销毁或者替换中间件(app.unuse)
- iOS中 UIMPMediaPickerController播放系统音乐
- hadoop启动 datanode的live node为0
- response.setContentType()的String参数及对应类型
- (转)Java transient关键字使用小记
- 助教日志—请沈航13级同学将GIT地址和CNBLOG地址发到这篇博文的评论中
- Regression Analysis Using Excel
- linux profile\bashrc\bash_profile之间的区别和联系
- Eclipse 安装spring插件spring tool suite(STS)
- Ant:Ant 入门
热门文章
- HTTP 错误 500.21 模块	IIS Web Core
- 【开源】使用Angular9和TypeScript开发RPG游戏(补充了Buffer技能)
- C# NAudio录音和播放音频文件及实时绘制音频波形图(从音频流数据获取,而非设备获取)
- python plt 色卡
- 洛谷5026 Lycanthropy 差分套差分
- Git入门操作(一)
- iOS UmbrellaHeader
- 作为 attribute 和 property 的 value 及 Vue.js 的相关处理
- 全网独家:成长经历分享 &; 我为什么要写书?
- binlog的作用及与redo log的区别