数论小总结

这几天学了一点数论算法，在这里进行一个小总结

扩展欧几里得，同余与模运算

欧几里得算法

首先先写一下基础的欧几里得算法

LL gcd(LL a,LL b)
{
    return b == 0 ? a : gcd(b,a%b);
}

证明还是先省省…记住gcd(a,b) == gcd(a%b,b)就足够了

扩展欧几里得算法

那么最关键的就是扩展欧几里得了。扩展欧几里得算法可以解出ax + by == gcd(a,b)的一组整数解，从而可以得出多组其他解。

void exgcd(LL a,LL b,LL &d,LL &x,LL &y)
{
  if(!b){d = a;x = 1;y = 0;}
  else {exgcd(b,a%b,d,y,x);y -= x*(a/b);}
}

具体过程是这样的：
原式: ax+by=gcd(a,b)(假设a≥b)

当b=0时有gcd(a,b)=a,此时x=1,y=0
当b不为0时,根据欧几里得定理gcd(a,b)=gcd(b,a % b)可得ax+by=gcd(a,b)=gcd(b,a % b)=bx′+(a % b)y′,即
ax+by=bx′+(a % b)y′=bx′+(a−b∗⌊a/b⌋)y′

移项得
ax+by=bx′+(a % b)y′=ay′+b(x′−⌊a/b⌋y′)

根据恒等定理,有
x=y′
y=x′−⌊a/b⌋y′
这有什么用呢?x′和y′还是不知道呀.
重新来看看我们得到的两个等式.x和y是gcd(a,b)=ax+by的解,而x’和y’是在对gcd(a,b)按欧几里德算法进行一步后的结果对应的贝祖等式gcd(b,a %b)=bx′+(a%b)y′的解.也就是说,gcd(a,b)对应的贝祖等式的解x,y可以由gcd(b,a%b)对应等式的解x’,y’计算得出
由于欧几里德算法最后一步为gcd(d,0)=d,此时对应的等式的解为x=1,y=0,因此只要如上述代码,从gcd(d,0)往前处理,在进行欧几里德算法的递归的时候根据相邻两次调用间x,y和x’,y’的关系计算即可求出ax+by=gcd(a,b)的解.
更进一步,对于任意不定式ax′+by′=c,只需要在等式ax+by=gcd(a,b)=d两边乘上c/d即可得到解为x′=x∗c/d,y′=y∗c/d

同余方程

考虑方程ax ≡ b(mod n),求解x
ax ≡ b (mod n ) 等价于 (ax - b) 是 n 的整数倍，即(ax - b) = ny,移项得 ax + ny = b,这样就可以运用扩展欧几里得解出一组解啦！
注意，扩欧解出来的是ax + ny = gcd(a,n),要求得答案还需要两边乘以(b / gcd(a,n))才行。由这一点我们可以显然得，若
(b % gcd(a,n)) != 0 则该同余方程无解！

逆元

考虑同余方程 ax ≡ 1(mod m)
我们称x为a的逆元.那么逆元有什么作用呢？
考虑式子(b / a) % m，由于是除号我们无法保证正确。这个时候我们可以找到a的逆元x，那么(b / a) % m == (b * x) % m
解法有很多，这里先写万能的扩欧方法，还有其他方法留坑

LL reverse(LL a,LL n)  //求a在模n下的逆元
{
  LL x,y,d;
  exgcd(a,n,d,x,y);
  return (d == 1) ? (x+n)%n : -1;  //必须保证a与n互质，否则逆元不存在
}

为什么要保证a与n互质？因为只有互质，gcd(a,n)才等于1。否则一旦gcd(a,n)大于1，肯定不与1同余了。

中国剩余定理 & 扩展中国剩余定理

在《孙子算经》中有这样一个问题：“今有物不知其数，三三数之剩二（除以3余2），五五数之剩三（除以5余3），七七数之剩二（除以7余2），问物几何？”这个问题称为“孙子问题”，该问题的一般解法国际上称为“中国剩余定理”。具体解法分三步：

1. 找出三个数：从3和5的公倍数中找出被7除余1的最小数15，从3和7的公倍数中找出被5除余1 的最小数21，最后从5和7的公倍数中找出除3余1的最小数70。
2. 用15乘以2（2为最终结果除以7的余数），用21乘以3（3为最终结果除以5的余数），同理，用70乘以2（2为最终结果除以3的余数），然后把三个乘积相加15∗2+21∗3+70∗215∗2+21∗3+70∗2得到和233。
3. 用233除以3，5，7三个数的最小公倍数105，得到余数23，即233%105=23233%105=23。这个余数23就是符合条件的最小数。

用算法的思想总结这三个步骤,假设三个除数分别为m1,m2,m3,余数分别为a1,a2,a3

1. 找出三个数，找出m2,m3的公倍数中模m1的逆元M1，m1,m3的公倍数中模m2的逆元M2，m1,m2的公倍数中模m3的逆元M3。
2. 将M1a1,M2a2,M3*a3，将他们相加在一起，得到SUM
3. SUM / LCM(m1,m2,m3),得到最小的解

同余系列模板

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long LL;
const int inf = 0x7fffffff;

LL gcd(int a,int b)
{
  return (!b) ? a : gcd(b,a%b);
}

LL lcm(int a,int b)
{
  return a / gcd(a,b) * b; //防止溢出
}
/*
扩展欧几里得:用于求ax + by = gcd(a,b) 的一组整数解
对于任意的解x  x = x0 + kb', 其中 b' = b / gcd(a,b)
所以 (x % b' + b') % b' 就是x的最小整数解，y同理
*/
void exgcd(LL a,LL b,LL &d,LL &x,LL &y)
{
  if(!b){d = a;x = 1;y = 0;}
  else {exgcd(b,a%b,d,y,x);y -= x*(a/b);}
}

LL reverse(LL a,LL n)  //求a在模n下的逆元
{
  LL x,y,d;
  exgcd(a,n,d,x,y);
  return (d == 1) ? (x+n)%n : -1;  //必须保证a与n互质，否则逆元不存在
}

LL CRT(LL *a,LL *m,int n)  //中国剩余定理，a是余数，m是除数，n是元素数量
{
  LL M = 1;
  LL ans = 0;
  for(int i=0;i<n;i++)  M *= m[i];
  for(int i=0;i<n;i++)
  {
    LL mi = M / m[i];
    ans = (ans + mi * reverse(mi,m[i]) * a[i]) % M;
  }
  if(ans < 0) ans += M;
  return ans % M;
}

LL EX_CRT(LL *a,LL *m,int n) //扩展中国剩余定理，采用合并的方式，可以解决m不互质的情况
{
  LL A = a[0];
  LL M = m[0];
  LL x,y,d,t;
  for(int i=1;i<n;i++)
  {
    exgcd(M,m[i],d,x,y);
    if((a[i] - A) % d)  return -1; // 同余无解，返回
    x *= (a[i]-A)/d,t = m[i]/d,x = (x%t+t)%t;  //求最小的一组整数解
    A = M*x+A,M = M/d*m[i],A %= M;  //更新A和M的值，注意求余
  }
  A = (A%M+M)%M;
  return A;
}