浅析逆元。扩展欧几里得，类欧几里得和莫比乌斯反演

逆元

扯一点没有多大用的东西

在数论里面，我们通常不把倒数叫做倒数，而叫做逆元（纯属装13）
逆元的作用是非常非常大的，下面我们来看点easy的栗子

某些性质

(a + b) \equiv a m o d p + b m o d p (m o d p)

(a - b) \equiv a m o d p - b m o d p (m o d p)

(a \times b) \equiv a m o d p \times b m o d p (m o d p)

前面三个都是对的~~（不需要证明~）~~
But——
$(a \div b) m o d p \neq ((a m o d p) \div (b m o d p)) m o d p$

（上面的÷是整除）

随便举个例子就知道它不成立

随便搞一下

这是不是说我们对除法下的大数模操作就毫无办法了？答案是no

为了方便，先来看看一些小学or初中级别的东东
比如说有条等式
$① a x = 1$
明显

② a x \equiv 1 (m o d p)

那么现在x就不一定等于
对于①式，我们就把x看成
这时候，我们不把x看成倒数。这时的x为a关于p的逆元

（注意，当且仅当

又是一个栗子

∵ (3 \times 5) m o d 7 = 1

∴ 3 \times 5 \equiv 1 (m o d 7)

逆元的蛋用

前面说了一些东东了
相信逆元的定义了应该很好懂
我们不妨把
$(a \div b) m o d p = (a \times i n v (b)) m o d p = (a m o d p \times i n v (b) m o d p) m o d p$

难搞的除法瞬间变成了乘法，秒变水了很多

逆元这东东怎么求

way one

基础数论里面有两条著名的定理：欧拉定理和费马小定理

欧拉定理：（当
费马小定理：（当

很明显，费马小定理是可以从欧拉定理推过来的

当p为质数时

既然我们在谈论逆元，就把费马小定理两边同除以一个p
$a p - 2 \equiv 1 / a (m o d p)$
attention to到一点就是
这时拍拍脑袋，想一想，我们突然发现应该把
so——

i n v (a) \equiv a p - 2 (m o d p)

我们可以用快速幂来求a的逆元，时间复杂度

code

long long inv(long long a,long long p)
{
    long long t=1,b=p-2;
    while (b)
    {
        if ((b%1)==1)t=t*a%p;
        a=a*a%p;
        b/=2;
    }
    return t;
}

通常题目会让你求

way two

逆元还可以用扩展欧几里得来求，怎么求？一步一步来

首先要知道一个概念：贝祖定理，他的描述是

对于

比如我们现在要求
代入贝祖定理，则
$a x + p y = 1$ （因为a和p互质所以
给上面那个式子做点操作，两边各模一个
$a x m o d p + p y m o d p = 1 m o d p$ $∴ a x m o d p = 1 m o d p$ $∴ a x \equiv 1 (m o d p)$
∴x是a关于p的逆元（其实

这里用扩展欧几里得

code

void exgcd(long long a,long long b,long long &x,long long &y,long long &z)
{
    if (!b) 
    {
        z=a;
        x=1;
        y=0;
        return;
    }
    exgcd(b,a%b,y,x,z);
    y-=x*(a/b);
}
long long inv(long long a,long long b)
{
     long long x,y;
     exgcd(a,b,x,y);
     return (x%p+p)%p;
}

扩展欧几里得可谓比较牛，优点是用途多，能求gcd能求逆元能解线性方程
对于广大OIers是把利器，学会是必须的

way three

最后一种方法更简单更好打更好理解：递归

先来一发证明~~（网上找的）~~

设 x = p m o d a ， y = p \div a

∴ (x + a y) m o d p = p m o d p = 0

∴ x m o d p = - a y m o d p

∴ x \cdot i n v (a) m o d p = (- y) m o d p

∴ i n v (a) = (p - y) \cdot i n v (x) m o d p

∴ i n v (a) = (p - p \div a) \cdot i n v (p m o d a) m o d p

有了这个等式，我们就可以用递归来求
递归出口

递归code

long long inv(long long a,long long p) //注意a要小于p，先把a%p一下 
{
    return a==1?1:(p-p/a)*inv(p%a,p)%p;
}

是不是短到爆炸？

因为
这种思想比费马小定理、扩展欧几里得优的地方是，他能用

只不过把递归的式子改成递推而已

递推code

void init()
{
    inv[1]=1;
    for(int i=2;i<=n;i++)
    {
        inv[i]=(p-p/i)*1ll*inv[p%i]%p;
    }
}

这是方法三，个人感觉方法三在某些题目里更好用一些

易理解，码量低，时间复杂度也低，还能快速预处理，interesting——

一笑

逆元差不多没得好说的了
三种求逆元的方法其实都挺好用的
虽说我倾向于第三种啦，这个东西多少随意
欸第二种方法里的的扩展欧几里得是什么？顺便看看？

扩展欧几里得

先复习一下普通欧几里得算法吧

普通欧几里得算法又称辗转相除法，为

~~我TM傻到连证明也要CO了~~
其实证明是没什么必要的，~~图个开心罢了~~

证明一发？

先设
设
把
设
公因数相同，最大公因数不也就相同了？

辣鸡code

long long gcd(long long x,long long y)
{
    return !y?x:gcd(y,x%y);
}

明显每
所以最坏时间复杂度为
但是我貌似查到欧几里得平均迭代次数为
算了随意随意……

还是要学扩欧的

咋们不搞正经的

a x + b y = c (a, b, c, x, y \in Z)

扩欧就是已经知道
明显的啊，想要有整数解的话，必须满足
不然两边各除以

不知道怎么求就给我右上角

设
但当
~~根据某恒等定理~~
所以
如此完美

不正经的code

long long exgcd(long long a,long long b,long long &x,long long &y)
{
    if (!b) 
    {
        x=1;
        y=0;
        return a;
    }
    long long ans=exgcd(b,a%b,x,y);
    int temp=x;
    x=y;
    y=temp-a/b*y;
    return ans;
}

~~其实差不多就是从上面CO过来的~~

直接调用exgcd(a,b,x,y)，结果是返回
同时求出来的

扩欧？有什么用？

扩欧一共有三种用途

purpose one

purpose two

purpose three

类欧几里得

随意随意

类欧几里得也是一种算法啦
它的样子很像欧几里得算法，所以叫做类欧
它可以解决
下面进入类欧的~~奇幻♂世界~~

三个函数和一个m

f (a, b, c, n) = \sum i = 0 n ⌊ a i + b c ⌋

g (a, b, c, n) = \sum i = 0 n i ⌊ a i + b c ⌋

h (a, b, c, n) = \sum i = 0 n ⌊ a i + b c ⌋ 2

m = ⌊ a n + b c ⌋

看官随便看看
反正类欧可以把这三个明显

~~您也知道鄙人数论不好，所以这坑要多久填完我不好说~~

下面的除法都看成整除，不再添加

求f

f (a, b, c, n) = \sum i = 0 n a i + b c

分类讨论大法好！

f (a, b, c, n) = \sum i = 0 n a i + b c = \sum i = 0 n 0 \cdot i +

= b c ( n + 1 )

f (a, b, c, n) = \sum i = 0 n a i + b c = \sum i = 0 n ( a c i +

= a c n ( n + 1 ) 2 + b c ( n + 1 ) + f ( a m o d c , b m o d c , c

f (a, b, c, n) = \sum i = 0 n a i + b c =

莫比乌斯反演

都说了度娘没用的还不信

呵呵莫比乌斯反演是数论数学中很重要的内容，在许多情况下能够简化运算,可以用于解决很多组合数学的问题
然而这仍旧没个卵用

网上并没有莫比乌斯反演的详细阐述，所以——
不墨迹，上车，飚上几圈再说

叫懵逼乌斯反演才对

首先定义
$f (n) = \sum d | n g (d)$
手推一波可以发现一些东东~~白内障看不清浓硫酸滴眼睛就放大了再看~~

- 莫比乌斯反演就是在已知
- 那么，我们可以试着用
  $g (n) = \sum d | n f (d) \times μ (n d )$
- 一脸懵逼？不知道
- 根据上面那个表可以得知，
- 用换元法设
  $g (n) = \sum d | n f (n t ) \times μ ( t ) = \sum d | n f ( n$

浅析逆元。扩展欧几里得，类欧几里得和莫比乌斯反演

逆元

某些性质

随便搞一下

逆元的蛋用

逆元这东东怎么求

way one

code

way two

code

way three

递归code

递推code

一笑

扩展欧几里得

先复习一下普通欧几里得算法吧

证明一发？

辣鸡code

还是要学扩欧的

咋们不搞正经的

不知道怎么求就给我右上角

不正经的code

扩欧？有什么用？

purpose one

purpose two

purpose three

类欧几里得

随意随意

三个函数和一个m

求f

a=0时

a≥c或b≥c时

a≤c且b≤c时

莫比乌斯反演

都说了度娘没用的还不信

叫懵逼乌斯反演才对