时间限制: 1 Sec  内存限制: 64 MB

题目描述

小蛇是金融部部长。最近她决定制造一系列新的货币。假设她要制造的货币的面值为x1,x2,x3… 那么x1必须为1，xb必须为xa的正整数倍（b>a）。例如 1，5，125，250就是一组合法的硬币序列，而1，5，100，125就不是。不知从哪一天开始，可爱的蛇爱上了一种萌物——兔纸！从此，小蛇便走上了遇上兔纸娃娃就买的不归路。某天，小蛇看到了N只可爱的兔纸，假设这N 只兔纸的价钱分别是a1,a2…aN。现在小蛇想知道，在哪一组合法的硬币序列下，买这N只兔纸所需要的硬币数最少。买兔纸时不能找零。

输入

第一行，一个整数N，表示兔纸的个数

第二行，N个用空格隔开的整数，分别为N只兔纸的价钱

输出

一行，一个整数，表示最少付的钱币数。

样例输入

2 25 102

样例输出

4

提示

样例解释：共有两只兔纸，价钱分别为25和102。现在小蛇构造1，25，100这样一组硬币序列，那么付第一只兔纸只需要一个面值为25的硬币，第二只兔纸需要一个面值为100的硬币和两个面值为1的硬币，总共两只兔纸需要付4个硬币。这也是所有方案中最少所需要付的硬币数。

 

1<=N<=50, 1<=ai<=100,000

 

题解

         虽然说是T1但是本着不会做就跳过的原则我还是果断把它忽略了……事实证明T3极其水，后来回来给这道题打了个dfs还有28分。刚开始以为是每一层的倍数都必须相同，然后自己在那里枚举得还挺high，后来发现不是那么回事，迷之尴尬。因为一贯是读完三道题，各自稍微想一下再开始按自己思路的有无集中做每一道题，所以有很多时候做完别的题再回来就对题意的理解出了偏差，下一次应该只要开始做就再读一遍题。

       有一个结论是每一层的倍数都应该枚举素数。因为发行硬币的种类是不限的，所以每一个合数都可以由很多素数的乘积得到。想象一下枚举第一个素数p1,那么a[i]%p1是一定要用一元硬币去买的。下一层再枚举一个素数p2,(a[i]-a[i]%p1)%(p1*p2)一定是要用p1去买的，这样每一层枚举之后把a[i]/=p,下一层就仍可以按这样的方式枚举，相当于秦九韶算法的逆运算，ans即为余数之和，深搜时可以比较当前的summod和ans来及时停止无意义的枚举。有一个我刚开始没注意到的优化是如果p已经大于当前最大的a[i],再枚举p是没有用的，直接把summod+=sigma(a[i])然后更新答案就可以停止当前dfs了。

 

#include
       
        #include
        
         #include
         
          #include
          
           using namespace std;const int sj=100005;int n,a[55],tp,z,jd,p[sj],ge;long long ans;bool nprime[sj];void dfs(int x,int st){     if(x>=ans) return;     int b[55];     memcpy(b,a,sizeof(b));     for(int i=1;i<=ge;i++)     {       tp=x;       if(a[n]
           
            =ans) break;       }       if(tp
            

()); dfs(0,1); printf("%lld",ans); return 0;}