在C ++中将N写为两个或多个正整数之和的方法

在这个问题上，我们得到一个整数n。我们的任务是找到in中可以表示为两个或多个正整数之和的总数。

让我们举个例子来了解这个问题，

输入值

N = 4

输出结果

5

说明

4 can be written as the sum in these ways,
4, 3+1, 2+2, 2+1+1, 1+1+1+1

为了解决这个问题，我们将使用欧拉的递推公式。对于数量n，可以通过以下方式生成它的总数：p(n)，

Σ∞n=0 p(n)xn = Π∞k=1 (1/(1-xk ))

使用此公式，我们将得出p(n)，p(n)= p(n-1)+ p(n-2)-p(n-5)-p(n-7)+…+（ -1）^(k-1)（（k(3k-1)）/ 2）

该程序说明了我们解决方案的实施情况，

示例

#include <bits/stdc++.h>
using namespace std;
long long postiveSum(int n){
   vector<long long> p(n + 1, 0);
   p[0] = 1;
   for (int i = 1; i <= n; ++i) {
      int k = 1;
      while ((k * (3 * k - 1)) / 2 <= i) {
         p[i] += (k % 2 ? 1 : -1) * p[i - (k * (3 * k - 1)) / 2];
         if (k > 0)
            k *= -1;
         else
            k = 1 - k;
      }
   }
   return p[n];
}
int main(){
   int N = 12;
   cout<<"The number of ways "<<N<<" can be written as sum of two or more positive numbers is "      <<postiveSum(N);
   return 0;
}

输出结果

The number of ways 12 can be written as sum of two or more positive numbers is 77