題意：

給出n個數，刪去其中一些使得總的gcd(最大公約數)最大

題目：

Mr. F has n positive integers, a1,a2,…,an.

He thinks the greatest common divisor of these integers is too small. So he wants to enlarge it by removing some of the integers.

But this problem is too simple for him, so he does not want to do it by himself. If you help him, he will give you some scores in reward.

Your task is to calculate the minimum number of integers you need to remove so that the greatest common divisor of the remaining integers is bigger than that of all integers.

Input

The first line contains an integer n (2≤n≤3?105) — the number of integers Mr. F has.

The second line contains n integers, a1,a2,…,an (1≤ai≤1.5?107).

Output

Print an integer — the minimum number of integers you need to remove so that the greatest common divisor of the remaining integers is bigger than that of all integers.

You should not remove all of the integers.

If there is no solution, print ?-1? (without quotes).

Examples

Input

3
1 2 4

Output

1

Input

4
6 9 15 30

Output

2

Input

3
1 1 1

Output

-1

Note

In the first example, the greatest common divisor is 1 in the beginning. You can remove 1 so that the greatest common divisor is enlarged to 2. The answer is 1.

In the second example, the greatest common divisor is 3 in the beginning. You can remove 6 and 9 so that the greatest common divisor is enlarged to 15. There is no solution which removes only one integer. So the answer is 2.

In the third example, there is no solution to enlarge the greatest common divisor. So the answer is ?1.

分析：

這道題的思路取自素數篩，甚至是歐拉篩，我們要刪除一些數字，
使得gcd增長，那么，我們就得把除去公共gcd之后的數進行一次篩選，
從最小的開始，我們求出那些個有相同質因數的數的數量的最大值。
舉個例子： 對于2 4 4 8 8 ； 他們的gcd=2，
除以2以后：1 2 2 4 4，我們從2開始遍歷“1～N”，
發現有4個是2的倍數，所以我們刪除的是N-4=1。
或許一個例子不夠形象： 對于3 6 6 9 ； 它們的gcd=3，
除以3以后：1 2 2 3，我們從2開始，2個是2的倍數， 1個是3的倍數，
之后5、7、11…沒有這樣的數了，所以刪除N-2==2即可。
思路就是這樣的。
特殊的，對于除完之后只剩下“1，1，1，1，…”這樣的數，我們直接printf("-1\n")。
注意：容易超時，得想辦法

AC代碼

#include<stdio.h> #include<string.h> #include<math.h> #include<algorithm> using namespace std; const int M=1.5e7+5; const int N=3e5+10; int sum[M]; int a[N],book[M]; int p[M],tot; void init() {memset(book,0,sizeof(book));for(int i=2; i<M; i++){if(!book[i])p[tot++]=i;for(int j=0; j<tot&&i*p[j]<M; j++)///減少復雜度{book[i*p[j]]=1;if(i%p[j]==0)break;}}/**for(int i=2; i<sqrt(M); i++){if(!book[i])p[tot++]=i;for(int j=i*2; j<M; j+=i)book[j]=1;}*/ } int main() {int n,x;scanf("%d",&n);init();int d=0;for(int i=1; i<=n; i++)//找到所有數的公因數{scanf("%d",&a[i]);d=__gcd(a[i],d);}for(int i=1; i<=n; i++){x=a[i]/d;///把所有的數都除以它們的gcd，則問題變為：保留最多的數，使得它們的gcd不等于1。for(int j=0; p[j]*p[j]<=x&&j<tot; j++)///枚舉gcd的時候可以只枚舉質數。可以通過線性篩將所有的質數O(n)時間復雜度篩出來{//除去公因數數之后將所有的數分解if(x%p[j]==0)sum[p[j]]++;//對素因數計數while(x%p[j]==0)x/=p[j];}if(x>1)sum[x]++;}int ans=0;for(int i=0; i<tot; i++)ans=max(sum[p[i]],ans);//找到最大的素因數出現次數if(ans==0)///假設所有數都等于1，顯然無解。printf("-1\n");elseprintf("%d\n",n-ans); } 創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的Enlarge GCD CodeForces - 1034A（欧拉筛+最大公约数）的全部內容，希望文章能夠幫你解決所遇到的問題。

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