Cod sursa(job #2503072)

Utilizator ripeanumihaiRipeanu Mihai ripeanumihai Data 2 decembrie 2019 12:19:23
Problema Dirichlet Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.77 kb
#include <iostream>
#include <fstream>
using namespace std;
const int MOD = 9999991;
ifstream f("dirichlet.in");
ofstream g("dirichlet.out");
void EuclidExtins(int a, int b, int &d, int &x, int &y)
{
    if(b == 0)
    {
        x = 1;
        y = 0;
        d = a;
    }
    else
    {
        int x0, y0;
        EuclidExtins(b, a % b, d, x0, y0);
        x = y0;
        y = x0 - (a / b) * y0;
    }
}
int inversmod(int a)
{
    int d, x, y;
    EuclidExtins(a, MOD, d, x, y);
    x %= MOD;
    if(x < 0) x += MOD;
    return x;
}
int main()
{
    int N;
    f >> N;
    int A = 1, B = 1;
    for(int i = 2; i <= N; i++)
    {
        A = 1LL*A * (N + i) % MOD;
        B = 1LL * B * i % MOD;
    }
    g << A*inversmod(B) % MOD;
    return 0;
}