当前位置： 移动技术网 > 移动技术>移动开发>Android > C. Orac and LCM

C. Orac and LCM

2020年07月08日  | 移动技术网移动技术  | 我要评论

文章目录

C - Orac and LCM

题意

给你 N 个数，让你求着 N个数任意两个数的lcm组成的 ** N*N/2 **个数的 gcd是多少；

解题思路

在这里插入图片描述

代码

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define fast ios::sync_with_stdio(0)
const int mx=100100;
ll g[mx];//求后缀gcd
ll a[mx];
int main()
{
	fast;
	int n;
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i]; 
	for(int i=n;i;i--){
		g[i]=__gcd(a[i],g[i+1]);	
	}
	ll ans=0;
	for(int i=1;i<=n;i++){
		ans=__gcd(ans,a[i]*g[i+1]/__gcd(a[i],g[i+1]));
	}
	cout<<ans<<"\n";
	return 0;
}

本文地址：https://blog.csdn.net/qq_43750980/article/details/107119103

您可能感兴趣的文章:

如对本文有疑问， 点击进行留言回复！！

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网