HackerRank Number Theory – Cheese and Random Toppings

Challenge: Cheese and Random Toppings

Subdomeniu: Number Theory (number-theory)

Scor cont: 30.0 / 30

Submission status: Accepted

Submission score: 1.0

Submission ID: 464724872

Limbaj: cpp14

Link challenge: https://www.hackerrank.com/challenges/cheese-and-random-toppings/problem

Cerinta

*Waiter:* Good day, sir! What would you like to order?  
*Lucas:* One Cheese & Random Toppings (CRT) pizza for me, please.  
*Waiter:* Very good, sir. There are $N$ toppings to choose from, but you can choose only $R$ toppings.     
*Lucas:* Hmm, let's see...  

...Then Lucas started writing down all the ways to choose *R* toppings from *N* toppings in a piece of napkin. Soon he realized that it's impossible to write them all, because there are a lot. So he asked himself: **How many ways are there to choose exactly $R$ toppings from $N$ toppings?**

Since Lucas doesn't have all the time in the world, he only wished to calculate the answer **modulo $M$**, where *M* is a squarefree number whose prime factors are each less than *50*.

Fortunately, Lucas has a Wi-Fi-enabled laptop with him, so he checked the internet and discovered the following useful links:  
[Lucas' theorem](http://en.wikipedia.org/wiki/Lucas'_theorem)  
[Chinese remainder theorem (CRT)](http://en.wikipedia.org/wiki/Chinese_remainder_theorem#Existence_and_uniqueness)  

**Input Format**  
The first line of input contains $T$, the number of test cases. The following lines describe the test cases.

Each test case consists of one line containing three space-separated integers: $N$, $R$ and $M$.  

**Constraints**  
$1 \le T \le 200$  
$1 \le M \le 10^9$  
$1 \le R \le N \le 10^9$  
$M$ is squarefree and its prime factors are less than $50$

**Output Format**  
For each test case, output one line containing a single integer: the number of ways to choose $R$ toppings from $N$ toppings, modulo $M$.  

**Sample Input**  
    
    6
    5 2 1001
    5 2 6
    10 5 15
    20 6 210
    13 11 21
    10 9 5    

**Sample Output**  

    10
    4
    12
    120
    15
    0
  
**Explanation**  

*Case 1 and 2*: Lucas wants to choose *2* toppings from *5* toppings. There are ten ways, namely (assuming the toppings are **A**, **B**, **C**, **D** and **E**):  

**AB**, **AC**, **AD**, **AE**, **BC**, **BD**, **BE**, **CD**, **CE**, **DE**  

Thus,  
*Case 1*: $10 \bmod 1001 = 10$  
*Case 2*: $10 \bmod 6 = 4$  



*Case 6*: We can choose *9* toppings from *10* by removing only one from our choice. Thus, we have ten ways and $10 \bmod 5 = 0$

Cod sursa

#include <bits/stdc++.h>
using namespace std;

#define SIZE 100
#define inv(a,m) fpow(a,m-2,m)

typedef long long int ll;
vector<int> primes;

void sieve() {
	char* s = new char [SIZE];
	int i, j;
	for (i = 2; i < SIZE; s[i++] = 1);
	s[0] = s[1] = 0;
	for (i = 2; i*i < SIZE; ++i) {
		if (s[i]) {
			for (j = i*i; j < SIZE; j += i) {
				s[j] = 0;
			}
		}
	}
	for (i = 2; i < SIZE; ++i) {
		if (s[i]) {
			primes.push_back(i);
		}
	}
	delete [] s;
}

ll fpow(ll a, ll b, ll mod) {
	ll res = 1;
	while (b) {
		if (b & 1)
			res = (res * a) % mod;
		b >>= 1;
		a = (a*a) % mod;
	}
	return res;
}

ll fact(ll r, ll mod) {
	ll res = 1;
	for (ll i = 2; i <= r; ++i) {
		res = (res * i) % mod;
	}
	return res;
}

ll comb(ll n, ll r, ll mod) {
	ll res = inv(fact(r, mod), mod);
	ll nf = 1;
	for (ll i = 0; i < r; ++i) {
		nf = (nf * (n-i)) % mod;
	}
	res = (nf * res) % mod;
	return res;
}

ll crt(vector<ll> a, vector<ll> p, ll mod) {
	/**
	 * Calculates CRT 'x' such that
	 * x = a1 (mod p1), x = a2 (mod p2), ...
	 * a is obtained from lucas
	 */
	ll x = 0, ni;
	for (int i = 0; i < p.size(); ++i) {
		ni = mod / p[i];
		x += ni * inv(ni, p[i]) * a[i];
	}
	return x;
}

ll lucas(ll n, ll r, ll p) {
	ll res = 1;
	while (n > 0) {
		res = (res * comb(n % p, r % p, p)) % p;
		n /= p;
		r /= p;
	}
	return res;
}

ll nCr(ll n, ll r, ll mod) {
	vector<ll> p;
	vector<ll> a;
	for (int i : primes) {
		if (mod % i == 0) {
			p.push_back(i);
		}
	}
	for (int i = 0; i < p.size(); ++i) {
		a.push_back(lucas(n, r, p[i]));
	}
	return crt(a, p, mod) % mod;
}

int main() {
	int t;
	ll n, r, mod;
	sieve();
	scanf("%i", &t);
	while (t--) {
		scanf("%lli %lli %lli", &n, &r, &mod);
		printf("%lli\n", nCr(n, r, mod));
	}
	return 0;
}