### Ma7moud's blog

By Ma7moud, history, 4 months ago, 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 ? Comments (16)
 » If $\gcd(x!, p) \ne 1$ then there is no modular inverse of $x! \pmod{p^e}$.
•  » » 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
 » 4 months ago, # | ← Rev. 4 →   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 integerAs 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 doFirst 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 productDivision 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 AlgorithmAnd 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
•  » » 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= 4P = 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) = 2qy = gcd (Y,M) = 4I wanna calculte X/Y % M We can calculte Px * modinvers Py since gcd (Py,M)=1For 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
 » This might be helpful — https://cp-algorithms.com/combinatorics/binomial-coefficients.html#mod-prime-pow
•  » » To be honest this link helped me a lot thanks
 » No idea how to solve it, but I know that Japanese can: Library-Checker
•  » » Before i see what is inside the link I am a big fan
•  » » » Thanks!
 » For nck mod m. If m is small, I feel like k cannot be that far away from n, otherwise binomial would become zero.
 » 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.
•  » » 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?
•  » » » 4 months ago, # ^ | ← Rev. 2 →   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$.
 » 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.
•  » » studying for exams at my college that's not interestingstudying adamant blog to solve combination problem ✓
 » 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