WCE0001 - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice

Author: Suyash Chavan
Editorialist: Suyash Chavan

DIFFICULTY:

EASY.

PREREQUISITES:

Modular Arithmetic

PROBLEM:

For each given testcase given number N find N! and 1/N! over mod M.

EXPLANATION:

  • As we know that modulus remains same for all test cases, for optimized approach we need to precompute the factorial and factorial inverse over the modulus and answer each query in O(1).
  • For computing inverse of factorial we need to precompute inverse of each natural number.

SOLUTIONS:

Setter's Solution 
#include<stdio.h>

long long fact[10000001];
long long inverse_fact[10000001];
long long natural_inverse[10000001];

int main() {
    long long t, mod;
    scanf("%lld %lld", & t, & mod);

    fact[0] = 1;
    fact[1] = 1;
    natural_inverse[0] = 1;
    natural_inverse[1] = 1;
    inverse_fact[0] = 1;
    inverse_fact[1] = 1;

    for (long long i = 2; i < 10000001; i++)
        fact[i] = (fact[i - 1] * i) % mod;

    for (long long i = 2; i < 10000001; i++)
        natural_inverse[i] = (natural_inverse[mod % i] * (mod - mod / i)) % mod;

    for (long long i = 2; i < 10000001; i++)
        inverse_fact[i] = (natural_inverse[i] * inverse_fact[i - 1]) % mod;

    while (t--) {
        long long n;
        scanf("%lld", & n);
        printf("%lld %lld\n", fact[n], inverse_fact[n]);
    }

    return 0;
}
1 Like
2

Fermat’s little theorem can be used alternatively in this question to calculate inverse as modulo is a prime number.

a ^ -1 ≅ a ^ m-2 (mod m) , where a^-1 is inverse and m is modulo and a prime number.

The power of the number(a) can be efficiently calculated using binary exponentiation.

3

Prime motive for this question was to get each query done in O(1). Using Fermat’s little theorem takes O(logN) time for each query.