Cod sursa(job #2384056)

Utilizator cyg_vladioanBirsan Vlad cyg_vladioan Data 20 martie 2019 10:20:53
Problema Dirichlet Scor 24
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.72 kb
#include <cstdio>
using namespace std;
const int M = 9999991;
long long Fast_pow(int a, int b)
{
    long long aa = a, p;
    for(p = 1 ; b ; b = b >> 1)
    {
        if(b & 1)
            p = (p * aa) % M;
        aa = (aa * aa) % M;
    }
    return p;
}
int main()
{
    freopen("dirichlet.in", "r", stdin);
    freopen("dirichlet.out", "w", stdout);
    int n, i, p, p1, p2, cat;
    scanf("%d", &n);
    p = 1;
    for(i = 1 ; i <= 2 * n ; i ++)
    {
        p = 1LL * (p * (i % M)) % M;
        if(i == n)
            p1 = p;
        if(i == n + 1)
            p2 = p;
    }
    cat = (1LL * p * Fast_pow(p1, M - 2) % M * Fast_pow(p2, M - 2) % M) % M;
    printf("%d\n", cat);
    return 0;
}