題干：

F先生有n個正整數，a1，a2，...，an

他認為這些整數的最大公約數太小了,所以他想通過刪除一些整數來擴大它

您的任務是計算需要刪除的最小整數數,以便剩余整數的最大公約數大于所有整數的公約數.

Input

3
1 2 4

Output

1

Input

4
6 9 15 30

Output

2

Input

3
1 1 1

Output

-1

題目大意：

n個數，要你刪掉最少的數，使得剩下的數的gcd大于所有n個數的gcd。
n<=3*10^5, 1<=ai<=1.5*10^7
解題報告：

從gcd入手，考慮gcd的本質是什么，不過就是所有n個數的公因子。所以可以想到可以從枚舉公因子的角度出發。

把所有的數都除以它們的gcd，那么這n個新數的gcd一定為1（常見套路），則問題變為：刪掉最少的數，使得它們的gcd不等于1。假設所有數都等于1，顯然無解。假設某一數不等于1，則只保留最大的這一個數 就是一個解， 所以一定有解。

我們先用cnt[i]表示a里面有多少個數等于i。

我們枚舉保留下來的數的gcd為p，則可以保留下來的個數為

可以發現，因此我們枚舉gcd的時候可以只枚舉質數。可以通過線性篩將所有的質數O(n)時間復雜度篩出來

最后那個枚舉的復雜度分析：

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define F first #define S second #define ll long long #define pb push_back #define pm make_pair using namespace std; typedef pair<int,int> PII; const int MAX = 3e5 + 5; const int MAXX = 1e7 + 5e6 + 5; int n,a[MAX],tot,p[MAXX],cnt[MAXX]; bool is[MAXX]; void prime() {memset(is,1,sizeof is);is[1]=is[0]=0;for(int i = 2; i<MAXX; i++) {if(is[i] == 0) continue;p[++tot] = i;for(int j = i+i; j<MAXX; j+=i) {is[j] = 0;}} } int main() {int g=0,ans = 3e5;cin>>n;for(int i = 1; i<=n; i++) scanf("%d",a+i),g = __gcd(g,a[i]);for(int i = 1; i<=n; i++) cnt[a[i]/g]++;if(cnt[1] == n) {cout << "-1" << endl;return 0 ;}prime();for(int i = 1; i<=tot; i++) {int sum = 0;for(int j = p[i]; j<MAXX; j+=p[i]) {sum += cnt[j];}ans = min(ans,n-sum);}cout << ans << endl;return 0 ; }

?

總結

以上是生活随笔為你收集整理的【CodeForces - 1047C】Enlarge GCD（数学，枚举，预处理打表，思维）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。