動的計画法、モジュラ計算、再帰の関数

最近コードフオースのの問題を解くために三つのテーマがある苦しい所を見ています。 A dynamic programming approach mapping the number of bits set in a number to its transforms to 1, the computation of a quotient mod m, and the ability to obtain recursive behavior without exhausting the stack are concerns. 再帰の数が多くてスタック空間が足りない心配があるがもっと効果的なアルゴリズムを考えられません。それ以外、モジュラに関わる割る処分がちょっと手数になる。The modular division operation requires the modular multiplicative inverse, which can be output by the extended Euclidean algorithm. This algorithm outputs gcd(a,b), which in this case will be the divisor k and the modular operand m. However, it also outputs x and y such that ax+by=gcd. As k and m are relatively prime, this simplifies to kx+ym = 1. Then, taking both sides mod m yields kx mod m + ym mod m = 1 (mod m). bm mod m is trivially 0. Thus, the equation is simply kx=1 mod m, so, given x from the algorithm, the modular multiplicative inverse of k is known. Then, to find (a/k)%m, take (a*x)%m.
参照
以下のサイトの説明に詳細が書かれています。
https://www.geeksforgeeks.org/multiplicative-inverse-under-modulo-m/
https://www.geeksforgeeks.org/modular-division/
The intuition behind the algorithm is a pair of recurrence relations and induction.
デバッグ用のログからのユークリッド計算の例を貼り付けます。calling exteuc on 8, 1000000007
extEuc end, retV 1, a 8, b 1000000007, x 125000001, y -1, rdr 0, quot 7
exteuc outputs jmodinv 125000001
calling exteuc on 9, 1000000007
extEuc end, retV 1, a 9, b 1000000007, x 111111112, y -1, rdr 0, quot 8
exteuc outputs jmodinv 111111112
もう一つの難しいところがあった。００１の場合に一ビットがありますが変換の数がゼロだからこのケースを変換一の合計から引くのが必要です。