【題解】LightOJ1067 逆元

題目連結

費小馬定理求逆元

a/b=1mod( M );

隻要 M 是一個素數，而且 b 不是 M 的倍數，就可以用一個逆元整數 b’，通過 a/b=a*b’*(mod M)來以乘換除

費馬小定理說，對于素數 M 任意不是 M 的倍數的 b，都有：b^(M-1)=1 (mod) M;

于是可以拆成：b*b^(M-2)=1(mod)M;

是以：a/b=a/b*(b*b^(M-2))=a*(b^(M-2))(mod M)

也就是說我們要求的逆元就是b^(M-2)(mod M)

#include<cstdio>
const int N=e6+;
const int mod=;
typedef long long ll;
ll fact[N];
void init()
{
    fact[]=fact[]=;
    for(ll i=;i<N;i++)
    fact[i]=(i*fact[i-])%mod;
}
ll niyuan(ll a,ll p)//快速幂 
{
    ll res=%mod;
    ll t=a%mod;
    while(p)
    {
        if(p%2)
        res=res*t%mod;
        t=t*t%mod;
        p/=;
    }
    return res;
}
ll work(int n,int k)
{
    ll fm=(fact[k]*fact[n-k])%mod;
    ll ans1=niyuan(fm,mod-);
    return (ans1*fact[n])%mod;
}
int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int t,n,k,ca=;
    init();
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&k);
        if(k*2>n)
        k=n-k;//組合數對稱性，減少計算
        printf("Case %d: %lld\n",++ca,work(n,k)); 
    }
}