Cod sursa(job #2070820)

Utilizator MikeStrikeAgache Mihai MikeStrike Data 19 noiembrie 2017 22:38:13
Problema Invers modular Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include <iostream>
#include <fstream>
#define P 20173333
using namespace std;
unsigned long long n,x,var,fact[100010];
ifstream in("sirul2.in");
ofstream out("sirul2.out");
void euclid(long long &x,long long &y,long long a,long long b)
{
if(!b) {x=1;y=0;}
else
{
    euclid(x,y,b,a%b);
    long long aux=x;
    x=y;
    y=aux-y*(a/b);
}

}
long long  combinari(long long  X,long long  Y)
{
    long long  i,r=1,t,inv=0,ins;
    r=fact[X];
    if (inv <= 0)
       inv = P + inv %P;
       euclid(inv,ins,fact[Y],P);
       if(inv<=0) inv=P+inv%P;
       i=inv%P;
       inv=0;
        euclid(inv,ins,fact[X-Y],P);
       if(inv<=0) inv=P+inv%P;
       t=inv%P;
    r=(r*i%P *t%P)%P;
    return r;
}

int main()
{
    in>>var>>n>>x;
 if(var==1) {fact[0]=1;
    for(int i=1;i<=100010;i++) fact[i]=(fact[i-1]*i)%P;
        out<<combinari(n-1,x-1);}

    return 0;
}