Cod sursa(job #3212407)

Utilizator and_Turcu Andrei and_ Data 11 martie 2024 18:17:09
Problema Invers modular Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.3 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("numere19.in");ofstream fout("numere19.out");
#define int long long
#define MOD 9973
int a,b,nr_sol;
int ans;
int ct[11];
int sol[11];
int factor[9009];

inline void Prod(int&x,int y)
{
    x= (1LL*x*y)%MOD;
}
inline int val_prod(int x,int y)
{
    return (1LL*x*y)%MOD;
}



void Generari()
{
    factor[0]=1;
    for(int i=1;i<=a;i++)
    {
        factor[i]=val_prod(factor[i-1],i);
//        cout << factor[i] << " ";
    }
}

inline int Invers_mod(int x)
{
    int val=1;
    int exp=MOD-2;
    while( exp )
    {
//cout << exp<<" ";
        if( exp%2==1 )
            Prod(val,x);
        Prod(x,x);
        exp/=2;
    }
    return val%MOD;
}


inline int Comb(int n,int k)
{
cout << val_prod(factor[n],Invers_mod(n-k)) << " "<< Invers_mod(k);
    return val_prod( val_prod(factor[n],Invers_mod(n-k)),Invers_mod(k) );
}

int32_t main()
{
//cout << 299238%MOD;
    fin >> a >> b;
    Generari();
cout << Comb(3,2);
return 0;
    for(int i=2;i*i<=b and b!=1;i++)
    {
        if( b%i==0 )
        {
            if( i>9 )
            {
                fout << 0 ;
                return 0;
            }
            while( b%i==0 )
            {
                ct[i]++;
                b/=i;
            }
        }
    }
    if( b!=1 )
    {
        fout << 0 ;
        return 0;
    }
    for(sol[4]=0;sol[4]<13;sol[4]++)
        for(sol[6]=0;sol[6]<13;sol[6]++)
            for(sol[8]=0;sol[8]<13;sol[8]++)
                for(sol[9]=0;sol[9]<13;sol[9]++)
                {
//                                                            return 0;
                    sol[5]=ct[5];
                    sol[7]=ct[7];
                    sol[2]=ct[2]-2*sol[4]-3*sol[8]-sol[6];
                    sol[3]=ct[3]-2*sol[9]-sol[6];
                    if( sol[2]<0 or sol[3]<0 )continue;

//                    cout << nr_sol ;
                    cout << sol[3] << " " << sol[9] << "\n";
                    int A=a;
                    nr_sol=1;
                    for(int i=2;i<=9 and A>=0;i++)
                    {
                        /// + rn
                        nr_sol= val_prod( nr_sol, Comb(A,sol[i]) );
                        A-=sol[i];
                    }
                    if( A<0 )
                        ans+=nr_sol;
                }
    fout << ans;
    return 0;
}