Project Euler 76

5は数の和として6通りに書くことができる:

4 + 1
3 + 2
3 + 1 + 1
2 + 2 + 1
2 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1
2つ以上の正整数の和としての100の表し方は何通りか.

悩んだ。@phylloさんのご助言により。

#include <iostream>
using namespace std;

// aを超えない値でbを分けたときの個数を返す
long long divnum(int a, int b){

	if(a==1 || b==1 || b==0) return 1;

	long long cnt = 0;
	for(int i=1 ; i<=b && i<=a ; i++){
		cnt+=divnum(i,b-i);
	}
	return cnt;
}

int main(){
	int n=100;

	long long cnt=0;
	for(int i=1 ; i<=n-1 ; i++){
		int tmp = divnum(i,n-i);
		cnt+=tmp;
	}

	cout << cnt << endl;

	int end;
	cin >> end;
}