2020智算之道初赛第一场 - 高校组 A.排队

A.排队

题目链接-A.排队


解题思路
$暴力$暴力

• 对于每个窗口的$a_i$ai​，我们可以for(int j=a[i];j<=n;j+=a[i])循环枚举$1-n$1−n范围内$a_i$ai​的倍数，然后用$vis[j]$vis[j]标记已经出队的人，以免后面重复计算
• 对于枚举到的$a_i$ai​的倍数且未被标记的编号，我们用cnt++记录，最后$n-cnt$n−cnt即为队伍中剩下的人数
• 具体操作见代码

附上代码

#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<bits/stdc++.h>
#define int long long
#define lowbit(x) (x &(-x))
#define endl '\n'
using namespace std;
const int INF=0x3f3f3f3f;
const int dir[4][2]={-1,0,1,0,0,-1,0,1};
const double PI=acos(-1.0);
const double e=exp(1.0);
const double eps=1e-10;
const int M=1e9+7;
const int N=2e5+10;
typedef long long ll;
typedef pair<int,int> PII;
typedef unsigned long long ull;
int a[N],vis[N]; 
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);

	int n,m,cnt=0;
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>a[i];
		for(int j=a[i];j<=n;j+=a[i]){
			if(!vis[j]){
				cnt++;
				vis[j]=1;
			}
		}
	}
	cout<<n-cnt<<endl;
	return 0;
}