## Multiplicative Function

A function $f(n)$ is called multiplicative function if:

1. $f(n)$ is defined for positive integer $n$.
2. $f(1) = 1$
3. $f(mn) = f(m)f(n)$ whenever $gcd(m,n) = 1$.

For example, the following functions are multiplicative:

## SPOJ ASCDFIB – Ascending Fibonacci Numbers

SPOJ ASCDFIB – Ascending Fibonacci Numbers is one of the earliest problems I created. This problem was used in one of the internal contests of Daffodil University. I was aiming for an easy, but a tricky problem and thus the following problem was created.

# Problem

Read the complete description of the problem from SPOJ ASCDFIB – Ascending Fibonacci Numbers.

Before you continue reading the rest of the post, please try to solve the problem on your own.

## Problem Summary

• Given $A \leq 10^5$ and $B \leq 10^6$
• Print from $fib(A)$ to $fib(A+B)$ in ascending order.
• $fib(n)$ is $n_{th}$ fibonacci number mod $10^5$.
• If there are more than $100$ terms in output, we need to print just the first $100$.
• There are $100$ test cases.
Read More

# Problem

Given non-negative integers $N$, $K$ and a prime number $P$, find the value of:

$$\binom{N}{K} \mod P$$

Sounds like a simple problem right? There are several ways to solve the problem, depending on the constraints of $N$, $K$, and $P$.

• Direct: If $N$, $K$ are really small, less than $12$, then we can calculate $\binom{N}{K}$ directly using formula $\frac{N!}{K! \times (N-K)!}$ and find the mod $P$ value. Not gonna work when the values are around $1000$.
• DP: If they are slightly bigger but still around $1000$, then we can use dynamic programming to find the result, using the recurrence: $\binom{N}{K} = \binom{N-1}{K} + \binom{N-1}{K-1}$. Not going to work if values are around $10^5$.
• Modular Inverse: If $P$ is a large prime, say $10^9+7$, then using modular inverse and some precalculation we can still calculate $\frac{N!}{K! \times (N-K)!}$. But still, we will need to run $O(N)$ loop to calculate $N!$. Not going to work if $N$ is too large. Also, if $P$ is small then there won’t be any modular inverse since $P$ will not be coprime with denominator anymore.

So what do we do when $N$ and $K$ are large (let’s say around $10^9$) and prime $P$ is small, let’s say $37$. Is it still possible?

Of course. We use Lucas Theorem.