NOIP2018 货币系统

一道看起来像数论题的完全背包问题。
幸好我前一天没有仔细看数论，使得我想的是写暴力…要不然我可能真的会推一个小时的\(EXGCD\)或\(CRT\)或者高斯消元之类的东西。
总之是小凯的疑惑迷惑了我，以为是一道数论题，所以到最后我都以为自己写的是暴力。
结果发现其实是正解思路的，已经写到了正解的倒数第二步，随便一优化就通过了。
但是始终以为是打暴力。
果然还是太菜了。
题意简述：你有\(n\)个正整数，要求，确定一个最小的\(m\)，使得用\(m\)种正整数数能够表示的数集与题目给出数能够表示的数集的完全一致。
首先我们证明一个定理：答案的\(m\)个数一定是原有数的子集。
下面我们分两类考虑这个问题。
如果新的数可以被原有数表示，那么显然它是没有意义的。
如果新的数不能被原有数表示，那么显然它是不合法的。
那么我们只需要考虑删除哪些数即可。
我们发现，一个数需要删除，当且仅当它可以被其他数表达出来。
反证法：如果它不可被其他数表示的话，那么删除它以后它就无法表示出来了。
并且，我们可以发现，这个问题满足最优子结构：如果一个数可以被当前的系统表达出来，那么删除当前系统中任意一些可以被表达出来的数，都不会导致这个数不能被表达出来。
故而，先删哪个其实都不影响答案的正确性。
因此我们可以从小往大删（可能可以节省时间）
暴力地考虑，我们需要枚举值域内每一个已经可以被表达出来的数，然后将这个数加上当前数的任意倍（值域范围内）
这么做最坏可能是\(O(T*n*a^2)\)的。
考虑优化。用欧拉筛的思想，对于每一个数，我们只需要加上当前数的一倍即可。
因为，如果加上当前数的两倍的话，就会在之后再一次访问到这个数，这时候就产生了访问次数上的浪费。
这样做是\(O(T*n*a)\)。
那就做完了。

#include<cstdio>
#include<iostream>
#include<algorithm> 
#include<cstring>

int n,a[105];
bool usf[25005];
void init(){
	std::memset(usf,0,sizeof(usf));
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d",a+i);
	}
	if(n==1){
		puts("1");
		return;
	}
	std::sort(a+1,a+1+n);
	int cnt=n;
	usf[0]=1;
	for(int i=1;i*a[1]<=25000;++i){
		usf[i*a[1]]=1;
	}
	for(int i=2;i<=n;++i){
		if(usf[a[i]]){
			a[i]=0;
			--cnt;
		}else{
			for(int j=0;j+a[i]<=25000;++j){
				if(!usf[j]){
					continue;
				}else{
					usf[j+a[i]]=1;
				}
			}
		}
	}
	printf("%d\n",cnt);
}
int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		init();
	}
	return 0;
}