C++에서 두 개 이상의 양의 정수의 합으로 N을 쓰는 방법

이 문제에서는 정수 n이 주어집니다. 우리의 임무는 두 개 이상의 양의 정수의 합으로 표현될 수 있는 방법의 총 수를 찾는 것입니다.

문제를 이해하기 위해 예를 들어보겠습니다.

입력

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