D1. Balance (Easy version)(暴力&数论)

D1. Balance (Easy version)(暴力&数论)

思路是开两个map，一个用于判断数是否出现在set中，另一个存每个数的k-mex。

假设当前我们要找的k对应的答案是x，那么我们利用map找答案的时候，必然会有$0,k,2k,\dots x-k,$一共$\frac{x}{k}$ 个数已经在set里了，因此如果k很小，那么插入操作次数就会很多，最后遍历的复杂度不会很高 ，因为$cn{t}_{add}+cn{t}_{query}=q$

但是存在$k_1,k_2,\dots$ 是同一个数的因子qwq，但是这种情况貌似复杂度不会很高，

#include 
using namespace std;
typedef long long ll;

ll i,j,k,n,m,t;

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	map<ll,ll> f,mp;
	mp[0]=1;
	
	cin>>t;
	while(t--){
		string s;
		cin>>s>>k;
		if(s=="+")mp[k]=1;
		else{
			while(mp[f[k]])f[k]+=k;
			cout<<f[k]<<'\n';
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24