Cod sursa(job #2107191)

Utilizator shantih1Alex S Hill shantih1 Data 16 ianuarie 2018 20:36:47
Problema Invers modular Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.67 kb
#include<iostream>
#include<fstream>
#define ll long long
using namespace std;
ifstream fin("sirul2.in");
ofstream fout("sirul2.out");
ll x,y,n,i,j,nr,U,R,RT,a,b,c,task,mod=20173333;
void invm(ll a,ll b,ll &x,ll &y)
{
	if(b==0)
	{	x=1; y=0;  return;}
	ll x0,y0;
	invm(b,a%b,x0,y0);
	x=y0;
	y=x0-(a/b)*y0;
}
int main(){
	
	fin>>task>>n>>nr;
	if(task==1)
	{
		U=nr-1;
		RT=n-1;
		nr=1; b=1; c=1;
		for(i=1;i<=RT;i++)
			nr=(nr*i)%mod;
		for(i=1;i<=U;i++)
			b=(b*i)%mod;
		for(i=1;i<=RT-U;i++)
			c=(c*i)%mod;

		invm(b,mod,x,y);
		if(x<0) x+=mod*(-x/mod)+mod;
		nr=(nr*x)%mod;
		invm(c,mod,x,y);
		if(x<0) x+=mod*(-x/mod)+mod;
		nr=(nr*x)%mod;
		fout<<nr<<"\n";
	}
	else fout<<0<<"\n";
}