数·论·小·结（1/2）

天泽龟 · 2018-07-28 01:44:27 · 个人记录

新的知识及时巩固QWQ！！

本章内容：EXGCD，逆元，剩余定理

• 拓展欧里几得

拓欧定理：

• 对于ax+by=gcd(a,b)的x,y有解且唯一。

证明：数学归纳

1. 对于(a,0)，显然ax=a的解是1(:з」∠)
2. 设 b<t 时，假设成立（回想起在老刘那里上课的场景QWQ）。
3. 当 b=t 时，存在bx+(a%b)y=gcd(b,a%b);（这步依赖了gcd的过程）。
4. 对于一般情况，则有

右式 =b*x+(a%b)y=bx+(a-[a/b]*b)*y

左式=gcd(b,a%b)=gcd(a,b)

5. 于是就得到一组解：x=y,y=x-[a/b]*y，其中内含的x,y均为上一层递归的答案。

程序：通过递归求解即可：

ll exgcd(ll a,ll b)
{
    if (!b) 
    {
        x=1,y=0; return a;
    }
    else{
        ll ans=exgcd(b,a%b);
        ll k=x;
        x=y; y=k-(a/b)*y; return ans;
    }
}

注意：对于一般柿子ax+by=c：

• 用拓欧要先求出ax'+by'=gcd(a,b)的解，
• 在通过x=x'*c/gcd(a,b)导出最后答案。
• 取模的时候要膜p/gcd(a,b)，貌似因为模数也缩小的关系？
• 如果gcd(a,b)|c成立才有解，反之没有。

• 求·逆·元（1）

定义：

• 对于一个计算函数f(x,y)，存在f(x,y)=1的那个y就是x的逆元，比如1+0=1的0,x*1/x=1的1/x，a/a中第二个a。

用途：

• 把不能用模运算的除法来换成乘上逆元，方便运算！

通式：a*a^-1=1(mod p)

1. 变个形式，ax=1(mod p)，是不是很像某年NOIP考题啊？
2. 求个exgcd(a,p)，其中的x就是a对于膜p下的逆元啦！
3. 因为ax+pk=1,所以当gcd(a,p)=1时，求出x,k的拓欧就是逆元

代码1：同上。

• 求·逆·元（2）

1. 先学一手费马小定理：a^{p-1} =1(mod p)
2. 所以：a^{p-2}*a =1(mod p)
3. 所以a^{p-2}就是a的逆元？但是必须在p为素数情况下！！

4. 再学一手快速幂，时间压到log(p)！！

快速幂代码（p-=2）：

ll ni(ll a,ll p,ll mo) //别忘膜P 
{
    ll ans=1,pp=p;
    a=a%mo;  //pow初始a 
    while (pp)
    {
        if (pp%2) ans=ans%mo*a%mo;
        a=a*a%mo; pp/=2;
    }
    return ans%mo;
}

• 求·逆·元（3）

  如果要求1~n的逆元，可以O(N)顺推。（n必须为素数）

参考这位dalao算法

• 设f(i)为i的逆元，则存在式子：f[i]=p-p/i*f[p mod i]
• 初始化f[1]=1，一边循环即可。

  #include <iostream>
  #include <cstdio>
  using namespace std;
  long long n,p,d[4000000];
  int main()
  {
    cin>>n>>p;
    d[1]=1; cout<<1<<endl;
    for (int i=2;i<=n;i++)
    d[i]=((-(p/i)*d[p%i])%p+p)%p,printf("%lld\n",(d[i]+p)%p);
    return 0; 
  }

中国剩余定理

若方程：

且a_1,a_2,a_3...a_n均互质，则一定存在唯一解：A_1*A_1^-*b1+A_2*A_2^-*b2+...A_n*A_n^-*bn，其中A^-为A的逆元,A_i为LCM/a_i。

• 证明

1.对于每一个i，只有A_i不包含a_i的因数，其余均约掉。

2.对于不能被约掉的A_i，在模a_i意义下乘上逆元,即可以把A_i约掉，只剩下b_i，存在一个解