Project Euler 53
12345から3つ選ぶ選び方は10通りである. 123, 124, 125, 134, 135, 145, 234, 235, 245, 345. 組み合わせでは, 以下の記法を用いてこのことを表す: 5_C_3 = 10. 一般に, r ≤ n についてn_C_r = n!/(r!(n-r)!) である. ここで, n! = n×(n−1)×...×3×2×1, 0! = 1と階乗を定義する. n = 23になるまで, これらの値が100万を超えることはない: 23_C_10 = 1144066. 1 ≤ n ≤ 100について, 100万を超えるn_C_rは何通りか?
C/C++
#pragma comment(lib,"mpir.lib") #include <mpir.h> #include <iostream> using namespace std; // 階乗(mpir版) void factorial(int n, mpz_t* ans){ mpz_init_set_ui(*ans, 1); for(int i=1 ; i<=n ; i++){ mpz_mul_ui(*ans,*ans, i); } } // combination(mpir版) void combination(int m, int n, mpz_t* ans){ mpz_t mf, nf, mnf; mpz_init_set_ui(*ans, 1); factorial(m, &mf); factorial(n, &nf); factorial(m-n, &mnf); mpz_mul(*ans, *ans, mf); mpz_div(*ans, *ans, nf); mpz_div(*ans, *ans, mnf); } int main(){ int m=23, n=10; mpz_t ans; int count=0; for(m=1 ; m<=100 ; m++){ for(n=1 ; n<=100 ; n++){ combination(m, n, &ans); //mpz_out_str(stdout, 10, ans); if(mpz_cmp_ui(ans, 1000000)>0) count++; } } cout << "count - " << count << endl; return 0; }
Project Euler 15ですでにcombinationは作ってたので、割と楽に。
ところで、環境が変わったらmpirの導入方法がわからなくて時間をくいました。
VC++10.0(VS2010)のライブラリ導入方法は、以下のページを参考にしました。
ライブラリの使用方法、VisualStudioの設定方法 画像処理ソリューション