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; }