傳送門
題目大意
給出一個序列 a a a，求出 g c d ( { l c m ( a i , a j ) ∣ i < j } ) gcd(\{lcm(a_i,a_j) | i<j\}) gcd({lcm(ai,aj)∣i<j})。
做法一
實際上不難發現序列中 a 1 a_1 a1對應的 l c m lcm lcm對為 n − 1 n-1 n−1對， a 2 a_2 a2對應的 n − 2 n-2 n−2對…以此類推，關鍵是如何化簡如下的表達式：
g c d { l c m ( a 1 , a 2 ) ， l c m ( a 1 , a 3 ) ， . . . ， l c m ( a 1 , a n ) } gcd \{ lcm(a_1,a_2)，lcm(a_1,a_3)，...，lcm(a_1,a_n) \} gcd{lcm(a1,a2)，lcm(a1,a3)，...，lcm(a1,an)}
GCD和LCM在質因數分解下的意義
假設 a a a經過質因數分解後為 P 1 k 1 ∗ P 2 k 2 , . . . ∗ P n k n P_1^{k_1}*P_2^{k_2},...*P_n^{k_n} P1k1∗P2k2,...∗Pnkn， b b b經過質因數分解為 Q 1 t 1 ∗ Q 2 t 2 , . . . ∗ Q n t n Q_1^{t_1}*Q_2^{t_2},...*Q_n^{t_n} Q1t1∗Q2t2,...∗Qntn
假設質因子 p p p為 a a a和 b b b共有的質因子，在 a a a中 p p p的幂次為 k 1 k_1 k1，在 b b b中 p p p的幂次為 k 2 k_2 k2，又因為所有的質因子兩兩互質，互不影響
那麼 g c d ( a , b ) gcd(a,b) gcd(a,b)的質因子 p p p實際上的幂次為 m i n { k 1 , k 2 } min\{ k_1,k_2 \} min{k1,k2}， l c m ( a , b ) lcm(a,b) lcm(a,b)的質因子 p p p實際上的幂次為 m a x { k 1 , k 2 } max\{ k_1,k_2 \} max{k1,k2}
那麼現在我們再看上式，對于所有數的一個公共的質因子 p p p，假設幂次分别為 k 1 , k 2 , . . . k n k_1,k_2,...k_n k1,k2,...kn，上式的意義為：
m i n { m a x ( k 1 , k 2 ) ， m a x ( k 1 , k 3 ) ， . . . ， m a x ( k 1 , k n ) } min \{ max(k_1,k_2)，max(k_1,k_3)，...，max(k_1,k_n) \} min{max(k1,k2)，max(k1,k3)，...，max(k1,kn)}
然後該式等價于：
m a x { k 1 ， m i n { k 2 , k 3 , . . . , k n ) } } max \{ k_1，min \{k_2,k_3,...,k_n) \} \} max{k1，min{k2,k3,...,kn)}}
即化為表達式：
l c m { k 1 ， g c d { k 2 , k 3 , . . . , k n } } lcm \{ k_1，gcd \{ k_2,k_3,...,k_n \} \} lcm{k1，gcd{k2,k3,...,kn}}
是以我們得到等式：
g c d { l c m ( a 1 , a 2 ) ， l c m ( a 1 , a 3 ) ， . . . ， l c m ( a 1 , a n ) } = l c m { k 1 ， g c d { k 2 , k 3 , . . . , k n } } gcd \{ lcm(a_1,a_2)，lcm(a_1,a_3)，...，lcm(a_1,a_n) \} = lcm \{ k_1，gcd \{ k_2,k_3,...,k_n \} \} gcd{lcm(a1,a2)，lcm(a1,a3)，...，lcm(a1,an)}=lcm{k1，gcd{k2,k3,...,kn}}
其它收獲
得知上述等式後，我們對左邊和右邊 l c m lcm lcm化 g c d gcd gcd得到：
然後兩邊約去 a 1 a_1 a1：
對于左式的分母，等價于 g c d { a 1 , g c d { a 2 , a 3 , . . . , a n } } gcd\{ a_1,gcd\{ a_2,a_3,...,a_n \} \} gcd{a1,gcd{a2,a3,...,an}}，那麼我們将 a 1 a_1 a1看做 x x x，将 g c d { a 2 , a 3 , . . . , a n } gcd\{ a_2,a_3,...,a_n \} gcd{a2,a3,...,an}看作 y y y，那麼左式實際上變成了：
y / g c d ( x , y ) y/gcd(x,y) y/gcd(x,y)
那麼，實際意義就是将 y y y和 x x x相同的最大公因數從 y y y中約去，而這時再看右式，不難發現實際就是将 y y y中的每一部分與 x x x相同的最大公因數約去，又因為 g c d gcd gcd運算和乘法的交換性（即 k ∗ g c d ( a , b ) = g c d ( k ∗ a , k ∗ b ) k*gcd(a,b)=gcd(k*a,k*b) k∗gcd(a,b)=gcd(k∗a,k∗b)）最後再求 g c d gcd gcd即約去了整體與 x x x的最大公因數
最後對于本題，我們隻需預處理字尾的 g c d gcd gcd即可
PS：本題的公式還可用另外方法證明，見mrcrack的部落格
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <math.h>
#include <cstdio>
#include <string>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
#define lowbit(x) (x&(-x))
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
const double eps=1e-8;
const double pi=acos(-1.0);
const int inf=0x3f3f3f3f;
const ll INF=1e18;
const int Mod=1e9+7;
const int maxn=2e5+10;
int a[maxn],sub[maxn];
ll gcd(ll a,ll b){
return b==0?a:gcd(b,a%b);
}
ll lcm(ll a,ll b){
return a/gcd(a,b)*b;
}
int main(){
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int n;
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
sub[n]=a[n];
for(int i=n-1;i>=1;i--)
sub[i]=gcd(sub[i+1],a[i]);
ll ans=0;
for(int i=1;i<=n;i++)
ans=gcd(ans,lcm(a[i],sub[i+1]));
cout<<ans<<endl;
return 0;
}
做法二
根據上述在質因數分解意義下的 g c d gcd gcd和 l c m lcm lcm，實際上就是需要求出 n n n個數中同時出現最少 n − 1 n-1 n−1次的質因子中幂次最大和次大的那個。
//
// Created by Happig on 2021/1/24.
//
#include <bits/stdc++.h>
#include <unordered_map>
#include <unordered_set>
using namespace std;
#define ENDL "\n"
#define lowbit(x) (x & (-x))
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
const double eps = 1e-8;
const double pi = acos(-1.0);
const int inf = 0x3f3f3f3f;
const double dinf = 1e300;
const ll INF = 1e18;
const int Mod = 1e9 + 7;
const int maxn = 2e5 + 10;
unordered_map<int, int> fi, se;
unordered_set<int> st;
int minp[maxn], prime[maxn], vis[maxn];
int cnt;
void euler() {
for (int i = 1; i < maxn; i++) minp[i] = i;
for (int i = 2; i < maxn; i++) {
if (minp[i] == i) {
prime[cnt++] = i;
}
for (int j = 0; j < cnt && i * prime[j] < maxn; j++) {
minp[i * prime[j]] = prime[j];
if (i % prime[j] == 0) break;
}
}
}
void divide(int n) {
map<int, int> mp;
int fac, p, num;
while (n > 1) {
fac = minp[n];
n /= fac;
mp[fac]++;
}
for (auto i:mp) {
p = i.first, num = i.second;
vis[p]++, st.insert(p);
if (!fi.count(p)) {
fi[p] = num;
continue;
}
if (!se.count(p)) {
if (num < fi[p]) {
se[p] = fi[p];
fi[p] = num;
} else se[p] = num;
continue;
}
if (num <= fi[p]) {
se[p] = fi[p];
fi[p] = num;
} else if (num < se[p]) {
se[p] = num;
}
}
}
ll qkp(ll x, ll n) {
ll ans = 1;
while (n) {
if (n & 1) ans = ans * x;
x *= x;
n >>= 1;
}
return ans;
}
int main() {
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n;
cin >> n;
euler();
for (int i = 1, x; i <= n; i++) {
cin >> x;
divide(x);
}
ll ans = 1;
for (auto p:st) {
//cout << p << ": " << fi[p] << " " << se[p] << ENDL;
if (vis[p] >= n - 1) {
if (vis[p] == n - 1) ans *= qkp(p, fi[p]);
else ans *= qkp(p, se[p]);
}
}
cout << ans << ENDL;
return 0;
}