題目鏈接：點(diǎn)擊查看

題目大意：給出 n 個(gè)數(shù)，先求出兩兩 lcm 后的集合 t ，再求這個(gè)集合 t 的 gcd

題目分析：做這個(gè)題得知道一個(gè)前置知識(shí)：對(duì)于 lcm 和 gcd 運(yùn)算來(lái)說(shuō)，每個(gè)質(zhì)因子都相互獨(dú)立

知道這個(gè)知識(shí)點(diǎn)后，對(duì)于每個(gè)數(shù)先質(zhì)因子分解，對(duì)于某個(gè)質(zhì)因子 p 而言，分三種情況討論：

如果 p 在 n 個(gè)數(shù)中均出現(xiàn)過(guò)，那么找到指數(shù)的次小值 k，其貢獻(xiàn)就是 p^k

如果 p 在 n - 1 個(gè)數(shù)中均出現(xiàn)過(guò)，那么找到指數(shù)的最小值 k，其貢獻(xiàn)就是 p^k

如果 p 在 n 個(gè)數(shù)中的出現(xiàn)次數(shù)小于 n - 1 ，其貢獻(xiàn)為 1

稍微解釋一下，因?yàn)閷?duì)于某個(gè)質(zhì)因子 p 來(lái)說(shuō)，如果先求 lcm 再求 gcd 的話，會(huì)給 gcd 造成影響的一定是指數(shù)最小的兩個(gè)數(shù)所求出的 lcm，而指數(shù)最小的兩個(gè)數(shù)所求出的 lcm 顯然就是指數(shù)次小的那個(gè)數(shù)的指數(shù)了

其實(shí)情況 2 和情況 1 類似，只不過(guò)是將情況 1 中的第 n 個(gè)數(shù)的指數(shù)用 0 代替了而已，這也情況 2 中的最小值不就是情況 1 中的次小值了嘛

當(dāng) p 在任意兩個(gè)數(shù)中的指數(shù)均為 0 時(shí)，此時(shí)次小值所代表的指數(shù)就是 0 了，貢獻(xiàn)為 p^0 = 1，為了降低復(fù)雜度將其視為沒(méi)有貢獻(xiàn)即可

最后將所有質(zhì)因子的貢獻(xiàn)累乘起來(lái)就是答案了，注意結(jié)果需要開(kāi) long long 儲(chǔ)存

代碼：

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=2e5+100;vector<int>p[N];void only(int n) {for(int i=2;i*i<=n;i++){if(n%i==0){int cnt=0;while(n%i==0){cnt++;n/=i;}p[i].push_back(cnt);}}if(n!=1)p[n].push_back(1); }LL q_pow(LL a,LL b) {LL ans=1;while(b){if(b&1)ans*=a;a*=a;b>>=1;}return ans; }int main() { #ifndef ONLINE_JUDGE // freopen("input.txt","r",stdin); // freopen("output.txt","w",stdout); #endif // ios::sync_with_stdio(false);int n;scanf("%d",&n);for(int i=1;i<=n;i++){int num;scanf("%d",&num);only(num);}LL ans=1;for(int i=1;i<N;i++){if(p[i].size()==n){sort(p[i].begin(),p[i].end());ans*=q_pow(i,max(p[i][0],p[i][1]));}if(p[i].size()==n-1){ans*=q_pow(i,*min_element(p[i].begin(),p[i].end()));}}printf("%lld\n",ans);return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的CodeForces - 1350C Orac and LCM(数论)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。