C. Orac and LCM
解题思路
数
论
数论
数论
- 对于
a
[
1
]
a[1]
a[1]，其产生的
l
c
m
lcm
lcm有
l
c
m
(
a
[
1
]
,
a
[
2
]
)
、
l
c
m
(
a
[
1
]
,
a
[
3
]
)
、
.
.
.
l
c
m
(
a
[
1
]
,
a
[
n
]
)
lcm(a[1],a[2])、lcm(a[1],a[3])、...lcm(a[1],a[n])
lcm(a[1],a[2])、lcm(a[1],a[3])、...lcm(a[1],a[n])，则它们的最大公因数
g
c
d
1
=
g
c
d
(
l
c
m
(
a
[
1
]
,
a
[
2
]
)
、
l
c
m
(
a
[
1
]
,
a
[
3
]
)
、
…
l
c
m
(
a
[
1
]
,
a
[
n
]
)
)
1=(lcm(a[1],a[2])、lcm(a[1],a[3])、…lcm(a[1],a[n]))
gcd1=gcd(lcm(a[1],a[2])、lcm(a[1],a[3])、…lcm(a[1],a[n]))
- 观察发现它们中的每一项都含有公因子
a
[
1
]
a[1]
a[1]，故
a
[
1
]
a[1]
a[1]必为
g
c
d
1
1
gcd1的因子，所以可化简为
g
c
d
1
=
l
c
m
(
a
[
1
]
,
g
c
d
(
a
[
2
]
,
a
[
3
]
,
.
.
.
a
[
n
]
)
)
1=lcm(a[1],(a[2],a[3],...a[n]))
gcd1=lcm(a[1],gcd(a[2],a[3],...a[n]))
- 同理可得
g
c
d
2
、
g
c
d
3
…
g
c
d
n
2、3…n
gcd2、gcd3…gcdn，那么答案可表示为
g
c
d
(
g
c
d
1
,
g
c
d
2
,
.
.
.
g
c
d
n
)
(1,2,...n)
gcd(gcd1,gcd2,...gcdn)
- 我们可以反向遍历数组
a[]，用suf[]数组储存后缀suf[] - 具体操作见代码
附上代码
#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<bits/stdc++.h>
#define int long long
#define lowbit(x) (x &(-x))
#define endl '\n'
using namespace std;
const int INF=0x3f3f3f3f;
const int dir[4][2]={-1,0,1,0,0,-1,0,1};
const double PI=acos(-1.0);
const double e=exp(1.0);
const double eps=1e-10;
const int M=1e9+7;
const int N=1e6+10;
typedef long long ll;
typedef pair<int,int> PII;
typedef unsigned long long ull;
int (int a,int b) {
return b?(b,a%b):a;
}
int a[N],suf[N];
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int n,ans=0;
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
for(int i=n;i>0;i--)
suf[i]=(a[i],suf[i+1]);
for(int i=1;i<=n;i++)
ans=(ans,suf[i+1]*a[i]/(suf[i+1],a[i]));
cout<<ans<<endl;
return 0;
}