1284.cpp

杭电 acm部分代码 有兴趣的可以下载 谢谢

#include <stdio.h>
void main()
{
    __int64 count;
    int n,leap,i,count1,count2;
    while(scanf("%d",&n)!=EOF){
        count=0;
        for(i=0;i<=n;i++){
            leap=0;
            count1=(n-i)/2.0;
            count2=(n-i)/3.0;
            if((n-i)%3==0)
                leap=1;
            count1=(count1-count2)+leap;
            count+=count1;
        }
    printf("%I64d\n",count);
    }
}
/*

         钱币问题，原帖如下：http://bbs.bc-cn.net/bbs/dispbbs.asp?BoardID=5&ID=44812&replyID=&skin=1
本来上次要上解答过程的，可一时疏忽给忘记了[em02]



         可能很多朋友对不定方程的解法都有一定的了解，我这里只针对钱币问题对一类简单的二元一次不定方程正整数解
做些简单说明，希望会对大家有用。
         （严谨的数学推理，要使用一些代数符号。在此为了简单起见，做个直接的例子，说明解答原理）
        这里先假设有1分，2分，3分硬币分别是z,x,y个，以下数学推理，请勿与程序表达式一概而论
                z+2x+3y=N(你需要键入的硬币总金额） 其中x,y>=0
                2x+3y=N-z------------------------------①
       设     m=N-z------------------------------------②
       综合①②  得
               2x+3y=m=m(3-2)
               2x+3y=-2m+3m
               2x+2m=3m-3y
               2(x+m)=3(m-y)
               (x+m)/3=(m-y)/2------------------------③
        由于2和3互质，所以③两边均是整数(若不是整数,则余数不一样)。不妨假设这个整数是t
               (x+m)/3=t     (m-y)/2=t
               x=3t-m          y=m-2t

         x，y>=0
               x=3t-m>=0    y=m-2t>=0
               t>=m/3---④   t<=m/2---⑤
         综合 ④ ⑤得
               m/3 <=  t  <=m/2
         到这里很显然，一个t对应一组（x,y) ，有几个t就有几组正整数解（请允许我包括0在内，本题要求）
   现在题目就转化成求区间[m/3,m/2]上整数的个数（t只要求整数，这范围是满足x,y取值的范围）
         (int)(m/2)-(int)(m/3)  是要求的个数吗？也许在有的时候是对的，但当m/3是整数的时候，显然少算了一个，那正是m/3本身
   题目到现在清楚了，当选择一个1分硬币的个数z, 那么N-z就确定了（即m)   计算出这时区间 [m/3,m/2]上整数个数，便是当1分
   硬币为z时，所有解的组数。那当然写程序，可以让1分硬币个数从0循环到N    计算出每次的组数，最后的总和便是本题的要求
   相信大家已经明白了，用这种方法有如下的程序
/*