C++で2つ以上の正の整数の合計としてNを記述する方法

この問題では、整数nが与えられます。私たちの仕事は、2つ以上の正の整数の合計として表現できる方法の総数を見つけることです。

問題を理解するために例を見てみましょう

入力

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