先看个简单的

Contest2274 - 抗击疫情，从我做起–大中小学生联合训练赛第五十九场

题目描述

输入

输出

样例输入 Copy

3 1
1 2 3

样例输出 Copy

3

提示

对于30%的数据,n<=20。
对于60%的数据,保证输入中所有数小于5000。
对于100%的数据,保证输入中所有数小于5e5,K<=n

• 对于各个题相对于下一个题较简单，这个题就是直接暴力枚举就完事了，先把把这些数的个数存放到数组中，这样好取用，就是找到最大的数（因为最大取这n个数时 最大就只能取到最大）
  然后往后筛就完了。

#include <map>
#include <queue>
#include <string>
#include<iostream>
#include<stdio.h>
#include<string.h>
#include <algorithm>
#include <math.h>
typedef long long ll;
using namespace std;
const int maxn=2e6+1010;
#define inf 0x3f3f3f3fconst
int mod=998244353;
const int MOD=10007;

inline int read() {
	int x=0;
	bool t=false;
	char ch=getchar();
	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
	if(ch=='-')t=true,ch=getchar();
	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
	return t?-x:x;
}

ll n,t,m,sum,maxx;
ll a[maxn],b[maxn],l[maxn],r[maxn];
char str[500][500],s[maxn];
int main() {
	cin>>n>>m;
	for(int i=1; i<=n; i++)
		cin>>t,a[t]++,maxx=max(maxx,t);
	for(int i=maxx; i>=1; i--){
		ll d=0;
		for(int j=i; j<=maxx; j+=i){
			if(j%i==0) d+=a[j];
		}
		if(d>=m) {
			cout<<i<<endl;
			return 0;
		}
	}
	return 0;
}

Contest2295 - 2020春季个人训练赛第五场

题目描述

输入

输出

样例输入 Copy

3
1 2 4

样例输出 Copy

1

提示

删去1这个数，最大公约数从1变到2。
对于30%的数据，n<=15
对于50%的数据，n,a_i<=1000
对于100%的数据，n<=300,000，a_i<=1.5*10^7

• 这个题相较于上个题要难，一是这个题的数据范围，二是这个题要使删后最大公约数，大于原本的对大公约数

• 其实这个题跟上个题还是有关系的，用到上个题的思想就是枚举，筛法，但这个绝对不会是像上个题那么容易，因为数据量给这摆着那，所以需要优化。

• 思路：求出原本的最大公约数(gcd) 这个是肯定的，(也可以不求，但是可能是常数较大，就比如最大公约数很大，就可以大大的优化时间）然后把所有数都除以这个最大公约数(gcd) .。所以还是求出来的好，然后是跟上个题的一样找出最大数，（这个最大数是1.5e7的 ），然后我们想到可以用上道题的筛法 ，你要找最大公约数就是用一个数(a)筛，如果这些数，能整除a那么a就是他们的公因数，（不一定是最大公因数）这个就相当于素数筛一样，所以我们只需要筛出<mark>根最大值</mark>就行，让后就是像上个题一样把这些数存放到数组，我们可以知道，这个数最大是1.5e7 ，所以我们无返佣下标表示这个数，就用<mark>为了减少复杂度，先排序，在比较前后两个数就行了，两个数组来表示，一个表示这个数的大小，一个表示这个数出现多少次</mark>这个地方也恶意用结构体，一样的。之后就是利用上题的筛法，这次是筛能否整除这些素数。中间有个地方要注意==有些数除以gcd后她并不在根最大值里面，而且这个数不是1，因为1不在我们筛出的素数中，所以它是单独的一个素数(大于根最大值)==不做这一步会被卡到91左右吧。
  最后就是结果，先考虑输出-1的情况。
  结合代码看一下吧。

#include <map>
#include<iostream>//ÏßÐÔɸËØÊý
#include<math.h>
#include<stdio.h>
#include<string.h>
#include <algorithm>
#define inf 0x3f3f3f3f
const int mod=998244353;
using namespace std;
const int maxn=2e6+10;

map<long long ,long long >mp;
bool a[maxn];
long long f[maxn],flag,cnt;
long long n,m,maxx,sum,b[maxn],c[maxn],e[maxn],d[maxn];

void prime(long long n){
	for(int i=2;i<=n;i++){
		if(a[i]==0) f[++cnt]=i;
		for(int j=1;j<=cnt&&i*f[j]<=n;j++)
		{
			a[i*f[j]]=1;
			if(i%f[j]==0) break;
		}
	}
}


long long  gcd(long long  a,long long b){
	while(b){
		long long t=a%b;
		a=b;
		b=t;
	}
	return a;
}

int main(){
	cin>>n;
	maxx=0;
	for(int i=1;i<=n;i++)
	{
		cin>>b[i];
		maxx=max(b[i],maxx);
		if(i==1) m=b[i];
		else m=gcd(m,b[i]);
	// mp[a[i]]++;
	}

	prime(sqrt(maxx/m)+2);
	
	b[0]=0;
	sort(b+1,b+1+n);
	for(int i=1;i<=n;i++)
		if(b[i]!=b[i-1]){
			++flag;
			d[flag]=b[i]/m;
			e[flag]=1;
		}else e[flag]++;
	
	for(int i=1;i<=flag;i++)
	{
		long long p=0;
		for(int j=1;j<=cnt;j++)
		{
			if(d[i]%f[j]==0) c[j]+=e[i],p=1;
		}
		if(p==0&&d[i]!=1){
			f[++cnt]=d[i];
			c[cnt]+=e[i];
		}
	}
	
	maxx=0;
	for(int i=1;i<=cnt;i++)
		maxx=max(maxx,c[i]);
	if(maxx==n||maxx==0) cout<<"-1"<<endl;
	else cout<<n-maxx<<endl;
	/* for(long long i=sqrt(maxx);i>m;i--){ long long d=0; for(long long j=i;j<=maxx;j+=i) if(j%i==0) d+=mp[j]; if(d>sum){ sum=d; } }*/
	
	return 0;
}