Cod sursa(job #1536162)

Utilizator robx12lnLinca Robert robx12ln Data 25 noiembrie 2015 20:02:52
Problema Invers modular Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 kb
#include<fstream>
#define MOD 30103
using namespace std;
ifstream cin("functii.in");
ofstream cout("functii.out");
long long n, s, a, b, c, ok, invsc, invsb;
void euclid( long long a, long long b, long long &x, long long &y ){
    if( b == 0 ){
        x = 1;
        y = 0;
    }else{
        long long x1 = 0, y1 = 0;
        euclid( b , a%b, x1, y1 );
        x = y1;
        y = x1 - a/b * y1;
    }
}
long long lgput( long long p){
    long long x = 2;
    long long r = 1;
    while ( p != 0 ){
        if( p % 2 == 1 ){
            r = r % MOD * x % MOD;
            r %= MOD;
        }
        x  = x % MOD * x % MOD;
        x %= MOD;
        p /= 2;
    }
    r -= 2;
    if ( r <= 0 ){
        r += MOD;
    }
    return r;
}
int main(){
    cin >> n >> s;
    a = 1;
    for( int  i = 2 ; i <= n ; i++ ){
        a *= i;
        a %= MOD;
    }
    b = 1;
    for( int  i = 2 ; i <= n - s ; i++ ){
        b *= i;
        b %= MOD;
    }
    c = 1;
    for( int  i = 2 ; i <= s ; i++ ){
        c *= i;
        c %= MOD;
    }
    euclid(b,MOD,invsb,ok);
    while( invsb <= 0 ){
        invsb += MOD;
    }
    euclid(c,MOD,invsc,ok);
    while( invsc <= 0 ){
        invsc += MOD;
    }
    ok = lgput(s);
    cout << (a * invsb % MOD * c % MOD * ok % MOD) % 100;
    return 0;
}