c++ - Cで100桁の数値mod10^ 9+7の値を見つける

Question

100桁の数字が与えられたとしましょう（入力は文字列にすることができます）。その数値％modの値を見つけたいと思います。ここで、modは10 ^ 9+7です。どうすれば答えを得ることができますか。文字列操作を使用して、多数の加算および減算関数をすでに実装しました。

前もって感謝します ！

Answer 1

¹⁰⁹は-1000000007を法とする-7です。

100桁の数字を右からN9桁のブロック（₀、a _{1 、...）に分割します。}我々は持っています：

N = a0 + a1*10^9 + a2*10^18 + ...

モジュラスは_0-7 * a ₁ + 49 *a2- _..です。

たとえば、87564875326485487234854862386245865486238654862をモジュロ1000000007で計算するとします。この数字の文字列を、右から9のブロックに分割します。

• a ₀ = 238654862
• a ₁ = 245865486
• a ₂ = 245865486
• a ₃ = 854862386
• a ₄ = 485487234
• a ₅ = 564875326
• a ₆ = 87

ここで、各ブロックを整数に変換し、m = a _0-7 * a ₁ + 49 * a _2-323 * a ₃ + ...を計算します（ヒント：64ビット整数を使用してください）。

今N = m (mod 1000000007)。