学步园

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <string>

using namespace std;

const int P = 7;

int N, M;

int fac[11111];

void facterial()
{
	fac[1] = 1;
	for (int i = 2; i < 11111; i++)
	{
		fac[i] = fac[i - 1] * i;
	}
}

int quick_pow(int a, int n)
{
	int ans = 1;
	while (n)
	{
		if (n & 1)
		{
			ans = (long long int)ans * a % P;
		}
		n >>= 1;
		a = (long long int) a * a % P;
	}
	return ans;
}

int extgcd(int a, int b, int &x, int &y)
{
	if (b == 0)
	{
		x = 1;
		y = 0;
		return a;
	}
	int d = extgcd(b, a % b, x, y);
	int t = x;
	x = y;
	y = t - (a / b) * y;
	return d;
}

int C(int n, int m)
{
	int x, y;
	int temp = extgcd((long long int)fac[m] * fac[n - m] % P, P, x, y);
	x = (x % P + P) % P;//这个还是比较重要的哈 
//	return (long long int)fac[n] * quick_pow((long long int)fac[m] * fac[n - m] % P, P - 2) % P;
	return (long long int)fac[n] * x % P;
}

int Lucas(int n, int m)
{
	if (m == 0)
	{
		return 1;
	}
	return (long long int)C(n % P, m % P) * Lucas(n / P, m / P) % P;
}

int main()
{
	facterial();
	while (scanf("%d%d", &N, &M) != EOF)
	{
		int t = N - M;
		int x, y;
		int d =extgcd(10, 5, x, y);
		cout << x << " " << y << endl;
		cout << d << endl;
		if (t < M)
		{
			M = t;
		}
		int ans = Lucas(N, M);
		cout << ans << endl;
	}
	system("pause");
	return 0;
}