一开始没什么思路...后来想到确定最大硬币面值就知道其他面值能取多少了。。而且结果是可以由较小的面值转移过来的。
f[i]表示最大面值为i时的最小硬币数。a[i]表示第i个物品的价钱。
f[i]=min{ f[ i / j ]- sum{ a[ k ] / i * ( j-1 ) } }，（j是i的因数）
对于物品k，我们能用a[k]/i 枚面值为i的硬币。显然肯定都用上啦。
而且现在我们用面值i 的硬币拼出来的价钱，本来肯定都是用面值为( i / j )的硬币拼的。（因为j是i的因数，所以能用( i / j )的拼；又因为( i / j )是之前的最大面额，所以肯定会用）
所以我们用a[k]/i枚面值为i 的硬币能够减少a[k]/i*(j-1)枚面值为( i / j )的硬币的使用。（感谢JSZX11556老司机指正。。已修改）
然后又因为显然，在符合条件的情况下面值种类越多越好（至少不会更差）。。所以我们使j为质数就好了。（若j是合数的话，我们可以先增加其他面额，然后从另一种面值转移到i，所以j不取合数对答案没影响）
线性筛质数的时候可以顺便求出每个数的最小质因数，然后就可以做到只枚举i的质因数了。
时间复杂度O(n*sum*loglogsum)，（sum为所有兔纸价钱的总和）（复杂度分析参考埃氏筛法= =）
#include<cstdio>
#include<iostream>
#include<cstring>
#define ll long long
using namespace std;
int mn[],pri[],f[],cnt,mx;
int a[];
bool cant[];
int i,j,k,n,m,ans; inline void prerun(int mx){
for(i=;i<=mx;i++){
if(!cant[i])pri[++cnt]=i,mn[i]=i;
for(k=i<<,j=;j<=cnt&&k<=mx;k=i*pri[++j]){
cant[k]=,mn[k]=pri[j];
if(!(i%pri[j]))break;
}
}
} int ra;char rx;
inline int read(){
rx=getchar(),ra=;
while(rx<''||rx>'')rx=getchar();
while(rx>=''&&rx<='')ra*=,ra+=rx-,rx=getchar();return ra;
}
inline int min(int a,int b){return a<b?a:b;} int main(){
// memset(f,60,(n+1)<<2);f[1]=0;
n=read();
for(i=;i<=n;i++)mx=max(mx,a[i]=read()),f[]+=a[i];
prerun(mx);
register int i,j,k,tmp,sm;
for(i=;i<=mx;i++)f[i]=f[];ans=f[];
for(i=;i<=mx;ans=min(ans,f[i]),i++)
for(tmp=i;tmp>;f[i]=min(f[i],sm)){
// printf(" %d %d\n",f[i],f[i/mn[tmp]]);
for(sm=f[j=i/mn[tmp]],k=;k<=n;k++)sm-=a[k]/i*(mn[tmp]-);
while(mn[tmp]==mn[tmp/mn[tmp]])tmp/=mn[tmp];tmp/=mn[tmp];
}
printf("%d\n",ans);
return ;
}