拓展欧几里得定理

Mar 8, 2021

简述

拓展欧几里得定理也称辗转相除法

公示表述：gcd(a,b)=gcd(b,a mod b)；

具体解释在代码里。

（沙雕一下：终极版本为求组合数）

补充知识点：

a / b % c != ((a % c) / (b % c)) % c

为了解决这个问题，出现了乘法逆元，若 b*x mod c=1,则 x 为 b 模 c 的乘法逆元

(a / b) % c = (a / b1) % c = (a / bbx) % c = ax % c

这样就会做了

代码示例

#include <stdio.h>
#define mod 1000000007
using namespace std;
//ax+by+c=0;有整数解当且仅当c=kgcd(a,b);
//ax+by=gcd(a,b) 先求;(x+b)%b是a关于模b的乘法逆元，前提是a，b互素
//ax+by=-c;的解为x0=-x/gcd(a,b)c y0=-y/gcd(a,b)c
//x'=x+k(b/gcd(a,b)) y'=y-k(a/gcd(a,b)); ax+by=gcd(a,b)的任意整数解
int table[1000005];
//计算阶乘表
void cal_table()
{
  table[0] = 1;
  for (int i = 1; i <= 1000000; i++)
    table[i] = table[i - 1] i % mod;
}
//解ax+by=gcd(a,b)，返回a，b的最大公因数
int extend_gcd(int a, int b, int &x, int &y)
{
  if (b0)
  {
    x = 1;
    y = 0;
    return a;
  }
  int r = extend_gcd(b, a % b, x, y);
  int t = x;
  x = y;
  y = t - a / b * y;
  return r;
}
//求a在模b下的乘法逆元（注意只有在a,b互素时才有乘法逆元）,若不存在逆元则返回-1
int inv(int a, int b)
{
  int x, y, d;
  d = extend_gcd(a, b, x, y);
  return (d1) ? (x + b) % b : -1; //因为x可能是负数，所以+b保证为正
}
//求组合数
int C(int n, int m)
{
  if (n < 0 || m < 0 || m > n)
    return 0;
  return table[n] inv(table[m], mod) % modinv(table[n - m], mod) % mod;
}
int main()
{
  int n, m;
  scanf("%d%d", &n, &m);
  cal_table();
  printf("%lld ", C(n, m));
  return 0;
}