x+2y+3z=n的非负整数解数

题目：给一个正整数n，范围是[1,10^6]，对于方程：x+2y+3z = n，其中x，y，z为非负整数，求有多少个这样的三元组

(x,y,z)满足此等式。

 

分析：先看x+2y=m，很明显这个等式的非负整数解数目为m/2 + 1，然后再看x+2y+3z = n，设k=n/3，那么它的解数目为：

ans = n/2+1+(n-3)/2+1+...+(n-3k)/2+1

 

所以就有：

LL Work(int n) {LL ans = 0;for(int i=0;i<=n/3;i++)ans += (n - 3*i)/2 + 1;return ans; }

进一步优化，我们不使用循环，直接合并，得到：

LL Work(LL n) {LL k = n/3;LL ans = (n+2)*(k+1) - 3*k*(k+1)/2;if(k%2!=0 && ans%2==0)ans -= k/2+1;elseans -= k/2;return ans/2; }

 

 

转载于:https://www.cnblogs.com/james1207/p/3354312.html

总结

以上是生活随笔为你收集整理的x+2y+3z=n的非负整数解数的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。