杭电1284-钱币兑换问题

  
2934
12553

  
718831
13137761
/*** 需要满足的条件 k1 + 2 * k2 + 3 * k3 = n* 原理:先确定硬币3的个数k3，每一个k3都能确定剩下的硬币换取方案，且不重复* k3确定之后k1, k2只需要满足 k1 + 2 * k2 = n - 3 * k3* 而满足这样的任意一个k2对应了一个k1，k2的范围为 0...(n-3 * k3) / 2，一共有(n-3 * k3) / 2 + 1 个*/
#include<iostream>
using namespace std;
int main()
{__int64 n,sum,i;while(cin>>n){sum=0;for(i=0;3*i<=n;i++){sum+=(n-i*3)/2+1;//把3分从0个到最大遍历就行了 }cout<<sum<<endl;}return 0;
}