同余与模算术

数论 2 Minutes

除法取模

trivial

当b|a时,有
\dfrac{a}{b}\bmod m=\dfrac{a\bmod bm}{b}
证明：
设\dfrac{a}{b}=km+x(x<m)
则a=kbm+bx
a\bmod bm=bx
\dfrac{a\bmod bm}{b}=x
所以\dfrac{a}{b}\bmod m=\dfrac{a\bmod bm}{b}
证毕。

untrivial

方程ax\equiv 1\pmod m的解称为a关于模m的逆元，记为a^{-1}\pmod m。当\gcd(a,m)=1时，方程有唯一解，否则无解。

于是\dfrac{a}{b}\bmod m可以转化为ab^{-1}\bmod m来计算。

显然，(a^{-1})^{-1}\equiv a\pmod m，(ab)^{-1}\equiv a^{-1}b^{-1}\pmod m

费马小定理

定理：若p是质数，且\gcd(a,p)=1，则a^{p-1}\equiv 1\pmod p。

此时a*a^{p-2}\equiv 1\pmod p，即a关于p的逆元为a^{p-2}。

快速幂

ll qPow(ll a,ll n,ll p)
{
  if (a==0) {
    return 0;
  }
  ll ans=1;
  a%=p;
  while (n) {
    if (n&1) {
      ans=ans*a%p;
    }
    a=a*a%p;
    n>>=1;
  }
  return ans;
}

扩展欧几里德算法

组合数取模

递推

Lucas定理

定理：若p为质数，对任意整数1\leq m \leq n，有
C_n^m\equiv C_{n\bmod p}^{m\bmod p}*C_{n/p}^{m/p}\pmod p

另一种形式：若p为质数，对任意整数1\leq m \leq n，有
C_n^m\equiv \prod_i C_{n_i}^{m_i}\pmod p
其中n_i和m_i分别表示n和m在p进制下第i位的值。

模板题－HDOJ3057

#include<bits/stdc++.h>
using namespace std;
using ll=long long;

const int MAXN=(int)1e5+10;
ll fac[MAXN];

void init(int p);
ll Lucas(ll n,ll m,ll p);
ll comb(ll n,ll m,ll p);
ll inv(ll a,ll p);
ll qPow(ll a,ll n,ll p);

int main()
{
  int T;
  cin>>T;
  while (T--) {
    int n,m,p;
    cin>>n>>m>>p;
    init(p);
    cout<<Lucas(n+m,m,p)<<endl;
  }
  return 0;
}

void init(int p)
{
  fac[0]=1;
  for (int i=1;i<p;i++) {
    fac[i]=fac[i-1]*i%p;
  }
}

ll Lucas(ll n,ll m,ll p)
{
  ll ans=1;
  while (n && m && ans) {
    ans=ans*comb(n%p,m%p,p)%p;
    n/=p;
    m/=p;
  }
  return ans;
}

ll comb(ll n,ll m,ll p)
{
  if (n<m) {
    return 0;
  };
  ll ans=fac[n]*inv(fac[m],p)%p*inv(fac[n-m],p)%p;
  return ans;
}

ll inv(ll a,ll p)
{
  return qPow(a,p-2,p);
}

ll qPow(ll a,ll n,ll p)
{
  if (a==0) {
    return 0;
  }
  ll ans=1;
  a%=p;
  while (n) {
    if (n&1) {
      ans=ans*a%p;
    }
    a=a*a%p;
    n>>=1;
  }
  return ans;
}

扩展Lucas定理

未知 的头像

发布者：风竹曦

已发布

留下评论