题意：
给定 \(n\) 种不同面值的纸币，面值为 \(a_1,\cdots ,a_n\)。问通过给钱和找零支付价格为 \(x\) 的商品至少共要多少张纸币
\(1=a_1<a_2<\cdots < a_n\le 1e18\)
\(a_i|a_{i+1}\)
思路：
\(dfs(x,S)\) 表示用面值集合 \(S\) 凑出 \(x\) 块钱最少要多少张。那么答案是 \(dfs(x,\{a_1,a_2,\cdots, a_n\})\)
先用 \(a_1\) 把 \(x\) 变成 \(a_2\) 的某个倍数 \(y\)，然后就要算 \(dfs(y,\{a_2,\cdots, a_n\})\)。这个过程是递归的
显然 \(y\) 要么是 \(\le x\) 的最大的 \(a_2\) 的倍数，要么是 \(\ge x\) 的最小的 \(a_2\) 的倍数。
我以为的 dfs 树：
graph x --> a["p=不大于x的最大的a<sub>2</sub>的倍数"] & b["q=不小于x的最小的a<sub>2</sub>的倍数"] a --> c["不大于p的最大的a<sub>3</sub>的倍数"] & d["不小于p的最小的a<sub>3</sub>的倍数"] b --> e["不大于q的最大的a<sub>3</sub>的倍数"] & f["不小于q的最小的a<sub>3</sub>的倍数"] c --> g1[...] & h1[...] d --> g2[...] & h2[...] e --> g3[...] & h3[...] f --> g4[...] & h4[...]实际上的 dfs 树：每一层最多只有两个不同结点
graph x --> p & q --> r & s --> t & u --> i[...] & j[...]这挺显然的。如果你觉得不显然，那我们证明一下：
graph x --> p & q p --> r1 & s1 q --> r2 & s2其中
\[p=\lfloor \frac x{a_2} \rfloor a_2 ,\ q = \lceil \frac x{a_2} \rceil a_2 \\ r1 = \lfloor \frac p{a_3} \rfloor a_3, \ s1 = \lceil \frac p{a_3} \rceil a_3 , \ r2 = \lfloor \frac q{a_3} \rfloor a_3, \ s2 = \lceil \frac q{a_3} \rceil a_3 \]注意到 \(s1=r1或s1=r1+a_3\)，\(s2=r2或s2=r2+a_3\)，那么
若 \(r1=r2\)，则 \(s2=s1或s2=s1+1\)，成立；
若 \(r1\neq r2\)，即
\[\lfloor \frac { \lfloor \frac x{a_2}\rfloor a_2 }{a_3} \rfloor a_3 \neq \lfloor \frac { \lceil \frac x{a_2}\rceil a_2 }{a_3} \rfloor a_3 \]记 \(a_3=ka_2(k>1)\)，则
\[\lfloor \frac { \lfloor \frac x{a_2}\rfloor }{k} \rfloor a_3 \neq \lfloor \frac { \lceil \frac x{a_2}\rceil }{k} \rfloor a_3 \]则 \(\lfloor \frac x{a_2}\rfloor = mk-1, \lceil \frac x{a_2}\rceil = mk(m>0)\)，则 \(s1=s2\)，则 \(r2=r1或r2=r1+1\)，得证
ll n, x, a[N];
map<ll, ll> f;
ll ceil(ll a, ll b) {
return (a + b - 1) / b;
}
ll dfs(ll x, ll i) { // O(n)
if(!x) return 0;
if(f.count(x)) return f[x];
if(i == n) return f[x] = x / a[i];
return f[x] = min( dfs(x / a[i+1] * a[i+1], i+1) + (x % a[i+1]) / a[i],
dfs(ceil(x, a[i+1]) * a[i+1], i+1) + (a[i+1]-(x%a[i+1]))/a[i] );
}
void sol() {
cin >> n >> x;
for(int i = 1; i <= n; i++)
cin >> a[i];
cout << dfs(x, 1);
}