货币系统
原题：（权限限制没有超链接——某省选培训部分分）
题目描述 Description
P国对其货币体系进行了更新，在新的体系下一共有N种货币，面值分别为a[1]，a[2]，……，a[N]。 一个货币体系是否合理，关键在于由这些货币所能构成的面值种类。由于P国的生产力限制，国民的单次消费总额不会超过M。现在P国国王想知道新体系下的货币能构成多少种M以内的面值。(每种面值的货币可以使用无限次)
输入描述 Input Description
输入文件的第一行为两个整数 N，M。 接下来1行N个整数，第i个数表示a[i]。
输出描述 Output Description
输出一个整数表示答案。
样例输入 Sample Input
2 10 2 7
样例输出 Sample Output
7
样例解释 Explanation
可以构成2,4,6,7,8,9,10这7种面值。
数据范围及提示 Data Size & Hint
个人解法：
踢开暴力直接跳标程（虽然我这也是部分分的标程……）。
今天算是学到了一个神奇的算法。
我们的任务是求出由a[1..n]的各种组合可以得到多少个数。
我们知道，不论是什么数，mod x的结果只有0..x-1这x种。
我们知道也知道，如果t是可以通过各种组合表示的，那么t+k*a[i]也是可以通过组合表示的。
那么接下来，我们便需要知道一个题设：
如果我们令x为a[i]中的一个，M[i]是可以被组合数当中，模x之后为i的最小的数。
那么sigma(m div M[i]*x+1)即为所有的可以组合的数的个数，其中0<=i<=x-1。
证明：
首先可以知道x是可以被组合的。
接下来，对于模x为i的所有的数，可以表示为M[i]+0,M[i]+x,M[i]+2x,M[i]+3x……M[i]+nx，其中M[i]+nx<=m且M[i]+nx+x>m
也就是说，M[i]+nx<=m
nx<=m-M[i]
n<=(m-M[i]) div x。
所以模x为i的数一共有(m-M[i]) div x+1个（即M[i]+[0..n]*x）。
这些数都是可以被组合的。而且所有可以被组合的数中，模x为i的数就是这些数。
所以将余数i从0到x-1枚举一遍，得到的sigma(m div M[i]*x+1)即为所有的可以组合的数的个数。
得证。
那么这个sigma就是我们的答案了。
现在问题是如何求出M[i]数组。
我们考虑使用最短路算法。
首先，0..x-1代表模x之后的余数。以这个意义来建立点0..x-1共x个点。
之后对于每一个点i，枚举a[1..n]，对于一个a[j]，我们建立一条边，从i到(i+a[j]) mod x，表示由模x为i变为模x为(i+a[j]) mod x可以通过加上a[j]来实现（废话……）。
那么我们从0开始跑一趟单源最短路。得到的dist[i]就是模x为i的M[i]。而模x为0的M[i]就是x了。
那么接下来统计就好了。
所以现在看来，我们的x取a[i]的最小值时间复杂度最优。
注意：存在有模x不可能等于i的情况，这个时候跳过就好。
用dijkstral的话，时间复杂度大概是O(n^2)。至于SPFA，恐怕就有点麻烦了。
代码如下：
uses math;
type
inf=record
x,w,next:longint;
end;
var
n,i,j,top:longint;
a,dist:array[0..2000] of int64;//a为题中给出面额，dist为单源最短路的储存数组。
map:array[0..2000,0..2000] of int64;//记录路径长度
flag:array[0..2000] of boolean;//dijkstral判重数组
x,m,ans:int64;
procedure dijkstral(i:longint);//最短路
var
vi,vj,vk,p:longint;
minn:int64;
begin
for vi:=0 to x-1 do
dist[vi]:=map[i,vi];
flag[i]:=true;
for vi:=1 to x-1 do
begin
minn:=maxlongint;
for vj:=0 to x-1 do
if not flag[vj] and (dist[vj]<=minn) then
begin
p:=vj;
minn:=dist[vj];
end;
flag[p]:=true;
for vj:=0 to x-1 do
dist[vj]:=min(dist[vj],dist[p]+map[p,vj]);
end;
end;
begin
read(n,m);
x:=4000;
for i:=1 to n do
begin
read(a[i]);
if a[i]<x then x:=a[i];//读入并找到最小的a[i]作为x
end;
fillchar(map,sizeof(map),124);//把map变成一个很大的数，这个数是8970181431921507452。
for i:=0 to x-1 do
for j:=1 to n do
map[i,(i+a[j]) mod x]:=min(map[i,(i+a[j]) mod x],a[j]);//添加路径
for i:=0 to x-1 do
map[i,i]:=0;
dijkstral(0);//求M数组（程序里其实就是dist数组）
dist[0]:=x;
for i:=0 to x-1 do//统计
if dist[i]<>8970181431921507452 then inc(ans,(m-dist[i]) div x+1);//如果i是模x不可能得到的，就不进行操作。
writeln(ans);//输出
end.
用最短路真的是我怎么也想不到的——在你只会暴力的时候别人用了图论，在你只敢仰望的时候别人已经傲视群雄。
这就是差距！
据说标程是用线段树来着？我要去学学。