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