Cod sursa(job #3249817)

Utilizator DunareTanasescu Luca-Ioan Dunare Data 17 octombrie 2024 23:02:01
Problema Combinari Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.09 kb
#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;
}