傳送門

文章目錄

• 目錄
• • 題意：
  • 思路：

目錄

題意：

給你一個(gè)長(zhǎng)度為$n$的數(shù)組，你每次可以選擇其中的兩個(gè)數(shù)，如果他們的$gcd$在數(shù)組中沒(méi)有出現(xiàn)那么就可以加在數(shù)組后面構(gòu)成一個(gè)新的數(shù)組，問(wèn)數(shù)組最長(zhǎng)是多少。

$2\le n\le 1e6,1\le a_i\le 1e6$

思路：

設(shè)$cnt[i]$表示包含因子$i$的數(shù)有多少個(gè)，但是想要判斷兩個(gè)數(shù)的$gcd==i$只靠$cnt[i]>1$是不夠的，因?yàn)椴荒鼙ＷC其中兩個(gè)數(shù)的最大公因數(shù)是$i$，但是我我們?nèi)绻杜e包含以$i$為因子的數(shù)$j$，如果存在$cnt[i]==cnt[j]$，那么一定不存在兩個(gè)數(shù)的最大公因數(shù)是$i$，因?yàn)檫@個(gè)時(shí)候這些數(shù)最大公因數(shù)是$j$。當(dāng)不存在上述情況且有兩個(gè)$x,y$滿足$cnt[x]>0,cnt[y]>0$，那么此時(shí)這兩個(gè)集合中的數(shù)最大公因數(shù)一定是$i$，直接$nlogn$求即可。

#include<bits/stdc++.h> #define X first #define Y second #define L (u<<1) #define R (u<<1|1) #define Mid (tr[u].l+tr[u].r>>1) #define pb push_back using namespace std;const int N=1000260,INF=0x3f3f3f3f,mod=1e9+7; typedef long long LL; typedef pair<int,int> PII;int n; int a[N],mp[N],cnt[N]; int gc[N];void solve() {scanf("%d",&n);for(int i=1;i<=n;i++) {scanf("%d",&a[i]);mp[a[i]]=1; cnt[a[i]]=1;}int ans=0;for(int i=1;i<=1e6;i++) {for(int j=i+i;j<=1e6;j+=i) {cnt[i]+=cnt[j];}}for(int i=1;i<=1e6;i++) {int flag=cnt[i]>0;for(int j=i+i;j<=1e6;j+=i) {if(cnt[i]==cnt[j]) flag=0;}ans+=flag;}printf("%d\n",ans-n); }int main() {int _=1;while(_--) {solve();}return 0; }

總結(jié)

以上是生活随笔為你收集整理的Codeforces Round #766 (Div. 2) D. Not Adding 数学gcd的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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