转自http://community.csdn.net/Expert/topic/3969/3969800.xml?temp=.384289

Problem Description:
There are three kinds of coins:1$,2$,3$.Given a chique of N$(0<n<=10^9),calculate the number of different ways to exchange the cheque.
Sample Input:1 2 3
Sample Outpt:1 2 3

也就是说，将N$的支票换为1$,2$,3$三种硬币，问有多少种换法?

1. gxqcn

记 #{A}表示集合 A 中元素的个数。以下 N 表示非负整数集。

S = #{(a,b,c)|3a+2b+c=M (a、b、c∈N)}
  = #{(a,b)|3a+2b≤M (a、b∈N)}
  = #{(a,b)|0≤b≤(M-3a)/2 (a、b∈N)}

(1)、当 M=2k(k∈N) 时，
     S = #{(a,b)|0≤b≤k-(3a)/2 (0≤a≤[M/3], a、b∈N)}
    (1.1)、当取 a=2t(t∈N) 时，
         S1 = #{(b,t)|0≤b≤k-3t (0≤t≤[M/6], b、t∈N)}
    (1.2)、当取 a=2t+1(t∈N) 时，
         S2 = #{(b,t)|0≤b≤k-3t-2 (0≤t≤[(M-3)/6], b、t∈N)}
    显然 S = S1 + S2，这里 S1、S2 可直接推导出公式来。

(2)、当 M=2k+1(k∈N) 时，同理类推。。。

也就是说，本题通过简单的数论和代数知识，直接得到公式，可以避免任何循环。

2. mathe()

long Partition(int M){
   int V=M/6,i,m=M%6;
   long c=3*V*V+3*V+1;
   if(m==0)return c;
   else return c+m*V+m-1;
}
很简单.首先考虑M是6的倍数的情况,
那么对于任意的y,z
2y+3z<=M我们都有一个解 x=M-2y-3z
所以我们只要数
2y+3z<=M,y>=0,z>=0的数目
而在M是6的倍数时,这个图像在平面上是一个三角形,而且三角形三个顶点都是格点
我们可以直接用格点三角形的面积来计算点的数目:
S=E/2+I-1,其中E表示边界上格点数目,I表示内部的格点数目.(其实直接数格点数目也好数)
而E很容易数出来,这样就可以算出I+E=3*V*V+3*V+1,(V=M/6)
然后,对于M关于6的余数不是0,我们只要计算
x+2y+3z=6V+1,6V+2,6V+3,...的数目就可以了.
分别对应
2y+3z<=6V+t的数目
这个在t=1时,是V个,对于t>1,是V+1个

评论