Pagini recente » Cod sursa (job #1168826) | Cod sursa (job #1215216) | Cod sursa (job #3287978) | Cod sursa (job #208767) | Cod sursa (job #3249817)
#include <bits/stdc++.h>
using namespace std;
ifstream f("inversmodular.in");
ofstream g("inversmodular.out");
int const MOD = 10e9 + 7;
int a, b;
void bezout(long long &x, long long &y, long long &d, int a, int b)
{
if(!b)
x = 1, y = 0, d = a;
else
{
bezout(x, y, d, b, a % b);
///swap(x,y);
x ^= y;
y ^= x;
x ^= y;
y = y - x * (a / b);
/*
int aux = x;
x = y;
y = aux - y * (a / b);*/
}
}
int main()
{
long long x = 0, y = 0, d, valcomb = 1, n, k ;
///Egalitatea lui Bezout:
///Exista x si y astfel incat
/// a * x + b * y = ( a, b) = d
f >> n >> k;
for(int i = n - k + 1; i <= n; i++)
valcomb=(valcomb*i)%MOD;
for(int i = 1; i <= k; i++)
{
x=y=0;
bezout(x, y, d, i, MOD);
if(x <= 0)
x = MOD - abs(x) % MOD;
valcomb=(valcomb*x)%MOD;
}
g << valcomb;
cout << x << '*' << a << '+' << y << '*' << b << '=' << d; /// afisam inegalitatea lui bezout
return 0;
}