Cod sursa(job #1366468)

Utilizator muraru_georgeMuraru George Cristian 323CB muraru_george Data 1 martie 2015 04:52:03
Problema Invers modular Scor 0
Compilator c Status done
Runda Arhiva educationala Marime 0.83 kb
#include <stdio.h>

#define p 30103


int power(int a, int b)
{
	if (b == 1)
		return a;
	
	if (b == 0)
		return 0;

	int tmp = b / 2;
	if (b % 2 == 1) {
		int rez = power(a * a, tmp);
		return rez * a;
	}

	return power(a * a, tmp);
}

void euclid(int a, int b, int *x, int *y)
{
	if (!b) {
		*x = 1;
		*y = 0;
	} else {
		int x0, y0;
		euclid(b, a % b, &x0, &y0);
		*x = y0;
		*y = x0 - (a / b) * y0;
	}
}

int main(void)
{
	FILE *f_in = freopen("functii.in", "rt", stdin);
	FILE *f_out = freopen("functii.out", "wt", stdout);

	int x, y, k, n, s;
	scanf("%d %d", &n, &s);
	
	int factorial[n+1];	
	factorial[0] = 1;

	int i;
	for (i = 1; i <= n; i++)
		factorial[i] = (i * factorial[i-1]);

	
	euclid(factorial[n - s] * factorial[s], p, &x, &y);
	while (x < 0)
		x += p;
	x *= factorial[n];
	x %= p;

	printf("%d", (x * (power(2, s) - 2)) % p);
}