modulo formula in C-CodePudding

I Have this formula: (n - 1)! ((n (n - 1))/2 ((n - 1) (n - 2))/4) 2<=n<=100000 I would like to modulate the result of this from this formula by any modulo, but for the moment let's assume that it is constant, MOD = 999999997. Unfortunately I can't just calculate the result and modulate it, because unfortunately I don't have variables larger than 2^64 at my disposal, so the main question is. What factors to modulate by MOD to get the results%MOD ? Now let's assume that n=19. What is in brackets is equal to 247.5

18! = 6402373705728000. (6402373705728000 * 247.5)mod999999997 = 921442488. Unfortunately, in case I modulate 18! first, the result will be wrong, because (18!)mod999999997 = 724935119. (724935119 * 247.5)mod9999997 = 421442490. How to solve this problem?

CodePudding user response：

I think the sum could be break down. The only tricky part here is that (n - 1)(n - 2)/4 may have a .5 decimal., as n(n-1) / 2 will always be integer.

S = (n - 1)!  * ((n (n - 1))/2   ((n - 1) (n - 2))/4)
  = [(n-1)!  * (n*(n-1)/2)]   [(n-1)! * (n-1)(n-2)/4]
  = A   B

A is easy to do. With B, if (n-1)(n-2) % 4 == 0 then there's nothing else either, else you can simplified to X/2, as (n-1)(n-2) is also divisible by 2.

If n = 2, it's trivial, else if n > 2 there's always a 2 in the representation of (N-1)! = 1x2x3x ... xN. In that case, simply calculate ((N-1)!/2) = 1x3x4x5x ... xN.

Late example:

N = 19
MOD = 999999997

--> 18! % MOD = 724935119 (1)
    (18!/2) % MOD = 862467558 (2)

    n(n-1)/2 = 171 (3)
    (n-1)(n-2)/2 = 153 (4)

--> S = (1)*(3)   (2)*(4) = 255921441723
    S % MOD = 921442488

On another note, if mod is some prime number, like 1e9 7, you can just apply Fermat's little theorem to calculate multiplicative inverse as such:

(a/b) % P = [(a%P) * ((b^(P-2)) % P)] % P (with P as prime, a and b are co-prime to P)

CodePudding user response：

You will have to use 3 mathematical formulas here:

(a   b) mod c == (a mod c   b mod c) mod c

and

(a * b) mod c == (a mod c * b mod c) mod c

But those are only valid for integers. The nice part here is that formula can only be integer for n >= 2, provided you compute it as:

 (((n - 1)! * n * (n - 1))/2)   (((n - 1)! * (n - 1) * (n - 2))/4)
    1st part is integer       |         2nd part is too

for n == 2, first part boils down to 1 and second is 0

for n > 2 either n or n-1 is even so first part is integer, and again eithe n-1 of n-2 is even and (n-1)! is also even so second part is integer. As your formula can be rewritten to only use additions and multiplications it can be computed