数学は大切です。組み合わせ数を求めるプログラム問題
問題です。
0< a <= b <= c <= d
10 = a + b + c + d
が成立する(a,b,c,d)の組み合わせは9つです。
1000000 = a + b + c + d
が成立する(a,b,c,d)の組み合わせ数は?
以下自分の解答コード
#include <stdio.h> #define N 1000000 /* 10 --> 9 100 --> 7153 1000 --> 6965278 10000 --> 6946527778 100000 --> 6944652777778 1000000 --> 6944465277777778 10000000 --> 6944446527777777778 */ int main() { long long E,k; long long ans = 0; for( E=2; E<=N/2; E++){ long long n=E/2; long long K = (3*E-N)/2; if( (double)n < (double)(3*E-N)/2.0)continue; if( K<1 )K=1; long long M = n-(K-1); ans += (N*M + (n*(n+1)-K*(K-1)) - 3*E*M)/2 + M - ((3*E-N)%2?M/2:0); } printf("ans: %lld\n",ans); return 0; }
割り算って怖い><
思わぬバグというか、自身の考えが至らず、微妙な誤差から抜け出せませんでした。
問題掲載の元サイトのリンクを張るべきなのだけど、どこで見たのか忘れてしまった。
上記は強引な解法だけど、もっとスマートな方法があるかもしれない。
というかきっとある…