When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

Ma7moud's blog

By Ma7moud, history, 10 months ago, In English

hello people! https://www.codechef.com/problems/SANDWICH I really tried to solve this problem I know I must factorize mod to its prime powers And solve some equations using crt but I don't know how to calculate mod inverse for x! Mod p^e where p is a prime p | mod since the gcd between x! and p is not equal to one any know how to calculate it ?

  • Vote: I like it
  • +24
  • Vote: I do not like it

»
10 months ago, # |
  Vote: I like it +18 Vote: I do not like it

If $$$\gcd(x!, p) \ne 1$$$ then there is no modular inverse of $$$x! \pmod{p^e}$$$.

  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    But how to solve the problem if i cant calculte mod invers May be mod is not a square free number because if mod is a square free numbers the problem will be easy and solvabe using locus theorm

»
10 months ago, # |
Rev. 4   Vote: I like it +30 Vote: I do not like it

I have an idea that I am not sure of (As I never tested it before), but you can try it.

Let the modulo of this problem be $$$M$$$. Initially, we will first have to prime factorize $$$M$$$, this can be done in $$$O(\sqrt{M})$$$, so we know all the primes which appear in the prime factorization of $$$M$$$

When you have an integer $$$x$$$ you can represent it as the product of two parts, one part is coprime with the $$$M$$$ and the other part consists as a product of primes from the prime factorization of $$$M$$$

Notice that the part non-coprime with $$$M$$$ is equal to $$$gcd(x,M)$$$, so the remaining part is equal to $$$\dfrac{x}{gcd(x,M)}$$$, let these two parts be $$$q$$$ and $$$p$$$ respectively, we are going to store $$$p$$$ as a normal integer

As for $$$q$$$, notice $$$q$$$ will only consist of product of primes from set of primes appearing in the prime factorization of $$$M$$$, there are at most $$$8$$$ such primes when $$$M≤10^6$$$, so we are actually going to store the prime factorization of $$$q$$$ as an array of exponents, where the $$$i-th$$$ element donates the exponent of $$$i-th$$$ prime in the prime factorization of $$$q$$$, the array size will not exceed $$$8$$$

I don't know how can you apply addition or subtraction to numbers when they are in this form, but you can apply multiplication and division like this :

let's suppose we have two numbers $$$x,y$$$ in the above form and we want to find their product $$$z$$$ modulo $$$M$$$ (also in the above form), here is what we are going to do

First for the $$$p$$$ part, we simple multiply the two parts together taken under modulo $$$M$$$, and you have the $$$p$$$ part for their product $$$z$$$

As for the $$$q$$$ part, we are just going to add the corresponding elements of the exponent arrays of $$$x,y$$$, which will result in the exponent array of their product

Division is similar to multiplication, if we want to calculate $$$\dfrac{x}{y}$$$, instead of multiplying the $$$p$$$ parts, we multiply the $$$p$$$ part of the $$$x$$$ by the inverse of the $$$p$$$ part of $$$y$$$, finding the inverse is possible by using the Extended Euclidean Algorithm

And as for the $$$q$$$ part, we subtract the corresponding elements of the exponent array of $$$y$$$ from the exponent array of $$$x$$$

If now you want to find the actual value of the number taken modulo $$$M$$$, you will evaluate the prime factorization using Fast Power (AKA Binary Exponentiation) and finally multiply the results of each prime by the $$$p$$$ part (All operations are under modulo $$$M$$$ here), and you will have your desired value

  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If think there is somthing wrong or i miss understood what u wrote I will write numbers interms of its prime divisors Let X = 2 *3 and Y = 2 *2 * 5 and Mod M= 4

    P = a / gcd(a,M) and q = gcd (a,M)

    Px= X/ gcd(X,M) = 3 * 2 / 2 = 3

    Py = Y / gcd(X,M) = 2 * 2*5 /4= 5

    qx = gcd(X,M) = 2

    qy = gcd (Y,M) = 4

    I wanna calculte X/Y % M We can calculte Px * modinvers Py since gcd (Py,M)=1

    For second part qx= 2 / prime is equal to 2 and its power = 1 qy = 4 / prime is equal to 2 and its power = 2 Since i need x/ y I will subtract power of x — power of y = 1 — 2 = -1 I wanna calculte 2 ^-1 mod M and M = 4 And gcd(4, 2) = 2 not 1 From that i cant calculate modinvers for 2

»
10 months ago, # |
  Vote: I like it +3 Vote: I do not like it
  • »
    »
    10 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    To be honest this link helped me a lot thanks

»
10 months ago, # |
  Vote: I like it +6 Vote: I do not like it

No idea how to solve it, but I know that Japanese can: Library-Checker

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For nck mod m. If m is small, I feel like k cannot be that far away from n, otherwise binomial would become zero.

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Suppose $$$n! = p^e \cdot x(x\perp p)$$$. We want to find $$$e$$$ and $$$x \bmod p^\alpha$$$.

$$$e$$$ is just $$$\sum_{i\geq 1}\lfloor{n\over p^i}\rfloor$$$. Let $$$M = \prod_{1\leq i < p^\alpha,i\perp p}i$$$, then $$$x(n) \equiv M^{\lfloor{n\over p^\alpha}\rfloor}x(\lfloor{n\over p}\rfloor)x(n \bmod p^\alpha)$$$, which can be calculated recursively.

  • »
    »
    10 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Can you tell me why this recurrence relation is correct before I write this post I searched a lot and found this recurrence relation but I don't know why this recurrence relation works I'm so glad you wrote it here to find out why this works Is this something related to locus theorm Or is it the generalization of locus theorm or what?

    • »
      »
      »
      10 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      You can simply classify the terms based on whether they have $$$p$$$ as a divisor, and get the product of each part. $$$M$$$ stands for the ones which don't have p, while $$$x(\lfloor{n\over p}\rfloor)$$$ stands for the ones which do. And there are $$$n\bmod p^\alpha$$$ extra numbers in the end.

      This method only works for small $$$p^\alpha$$$.

»
10 months ago, # |
  Vote: I like it +15 Vote: I do not like it

Hey, I wrote a blog recently just about that! Essentially, you just compute a pair $$$(k, a)$$$ such that $$$n! = p^k a$$$, where $$$\gcd(a, p) = 1$$$. Then you can cancel out the powers of $$$p$$$, and for co-prime parts you just compute inverses as usual.

  • »
    »
    10 months ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    studying for exams at my college that's not interesting

    studying adamant blog to solve combination problem ✓

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can't we just do find n! mod m then find ((n-r)! mod m * (r)! mod m) then find inverse of this number and multiply by n! taking mod