Codeforces Round #641 (Div. 2)-C. Orac and LCM(数论,gcd,lcm)

题目链接

题意:

给你一个数组,求数组中所有元素之间的lcm的gcd。

思路:

公式推理题(暴力跑铁定T),最终你可以推理得到这个公试:GCD(LCM(a,b),LCM(a,c))=a*GCD(b,c)/GCD(a,b,c);
所以你只需要求出一个元素之后所有元素的GCD,再放入公式就可以得出答案了。

代码:

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
const int N=1e6+5;
const int inf=0x3f3f3f3f;
int gcd(int a,int b)
{
	return b?gcd(b,a%b):a;
}
signed main()
{
    IOS;
    int n,arr[100005],brr[1000005];
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>arr[i];
    }
    brr[n]=arr[n];
    brr[n-1]=gcd(arr[n],arr[n-1]);
    int sum=arr[n]/brr[n-1]*arr[n-1];
    for(int i=n-2;i>=1;i--)
    {
        brr[i]=gcd(brr[i+1],arr[i]);
        sum=gcd(sum,arr[i]/brr[i]*brr[i+1]);
    }
    cout<<sum<<endl;
    return 0;
}

上一篇:Codeforces Round #729 (Div. 2) 补题 A B C


下一篇:C. Fadi and LCM