G2020 19寒假集训Day4

信息学——19寒假集训

---

今天是G2020寒假集训Day4了，数学专题终于来了，主讲数论。

1.最小公倍数与最大公因数

$1^o$ 定义

定义如下：

最大公因数(gcd):多个数的公共因数中最大的数
最小公倍数(lcm):多个数的公共倍数中最小的数

$2^o$ 最小公倍数的性质

性质1：

我们一般用$gcd$来表示$lcm$

$$\operatorname{lcm}(a,b)=\frac{ab}{\gcd(a,b)}$$

性质1推论：

$lcm(a_1,a_2,a_3,\cdots,a_n)$的表示方法:

设：$S$为$a_1,a_2,\cdots,a_n$的集合。

则

$$\operatorname{lcm}(S)=\prod_{T\in{S}}{\gcd(T)^{(-1)^{|T|+1}}}$$

$3^o$ 最大公因数的性质

性质1：

$$\gcd(Fib(a),Fib(b))=Fib(\gcd(a,b))$$

性质2：

$$\gcd(x^a-1,x^b-1)=x^{\gcd(a,b)}-1$$

2.欧几里得与拓展欧几里得

$1^o$ 欧几里得算法

欧几里得算法是求$\gcd$的一种方法，其核心为：

$$\gcd(a,b)=\gcd(b,a\bmod b)$$

根据此式不断递归，缩小$a,b$，此算法又称辗转相除法。

$2^o$ 拓展欧几里得算法

拓展欧几里得适用问题：

给定$a,b$求一组$x,y$满足$ax+by=\gcd(a,b)$的解

拓展欧几里得的内容:

若：有$x_0,y_0$满足：

$$b*x_0+(a\bmod b)*y_0=gcd(b,a\bmod b)$$

则有一组特殊解：

$$x=y_0$$

$$y=x_0-\lfloor{\frac{a}{b}}\rfloor*y_0$$

证明如下：

设$x_0,y_0$满足：

$$b*x_0+(a\bmod b)*y_0=\gcd(b,a\bmod b)$$

整理得：

$$a*y_0+b*(x_0-\lfloor{\frac{a}{b}}\rfloor*y_0)=\gcd(a,b)$$

对比方程：

$$ax+by=\gcd(a,b)$$

所以有：

$$ax+by=a*y_0+b*(x_0-\lfloor{\frac{a}{b}}\rfloor*y_0)$$

所以易得：

$$x=y_0$$

$$y=x_0-\lfloor{\frac{a}{b}}\rfloor*y_0$$

$3^o$ 拓展欧几里得求整数解系

我们之前已经求出了一组特殊整数解。

但是如果要我们求出所有解怎么办呢？

我们可以考虑不定方程求解系的做法。

由于我们已经得到了一组特殊解，则整个解系为：

$$x=x_0+k*\frac{b}{\gcd(a,b)}$$
$$y=y_0-k*\frac{a}{\gcd(a,b)}$$

这是不定方程的基本知识，不再赘述。

$4^o$ 拓展欧几里得解不定方程

拓展欧几里得多用于解，形如$ax+by=c$的不定方程

我们首先要知道，此方程有整数解的充分条件为：

$\gcd(a,b)\mid c$

那么我们可以考虑先求出$ax+by=\gcd(a,b)$的解。

直接使用拓展欧几里得定理即可。

那么只需要将$x$，$y$分别乘上$\frac{c}{\gcd(a,b)}$。

//The code is from dxbdly
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
    int x=0;
    char c=getchar();
    bool f=0;
    while (!isdigit(c))
          f=f|(c=='-'),c=getchar();
    while (isdigit(c))
          x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return f?-x:x;
}
inline int get_gcd(int a,int b)
{
    return !b?a:get_gcd(b,a%b);
}
inline void Exgcd(int a,int b,int &x,int &y)
{
    if (!b)
       x=1,y=0;
    else
       Exgcd(b,a%b,y,x),y-=a/b*x;
}
int main(){
    int a,b,c,x,y;
    a=read(),b=read(),c=read();
    Exgcd(a,b,x,y);
    printf("%d %d",x*c/get_gcd(a,b),y*c/get_gcd(a,b));
    return 0;
}

3. 乘法逆元

$1^o$ 逆元定义

若 $a*x\equiv1\pmod b$，则称$x$为$a$在$\bmod b$意义下的逆元，记为$a^{-1}$，也可以说$x$是$a$在$\bmod b$意义下的倒数。

大多数求逆元的方法都要求$\gcd(a,b)=1$且$b$为质数。

求解逆元的方式有很多，下面给出4种求法。

$2^o$ 拓展欧几里得求逆元

注意此算法只要求$\gcd(a,b)=1$，$b$不一定为质数。

使用拓展欧几里得求解逆元是很好的选择，他的速度比其他算法稍快，并且适用性比较广。

我们可以将同余方程$a*x\equiv1\pmod b$变为不定方程$a*x+b*y=1$

求解这个方程的解直接套用拓展欧几里得就可以了。

//The code is from dxbdly
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
    int x=0;
    char c=getchar();
    bool f=0;
    while (!isdigit(c))
          f=f|(c=='-'),c=getchar();
    while (isdigit(c))
          x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return f?-x:x;
}
inline void Exgcd(int a,int b,int &x,int &y)
{
    if (!b)
       x=0,y=1;
    else
       Exgcd(b,a%b,x,y),y-=a/b*x;
}
int main(){
    int a,b,x,y;
    a=read(),b=read();
    Exgcd(a,b,x,y);
    x=(x%b+b)%b;
    printf("%d",x);
    return 0;
}

$2^o$ 费马小定理求逆元

这个算法需要用到费马小定理：

$a^{b-1}\equiv 1\pmod b$，其中$\gcd(a,b)=1$，且$b$为质数

（后面的章节有详细讲解）

可以发现此同余式右边正好为$1$，且都是$\bmod b$意义下的。

考虑将原式的$1$替换，则：

$$a*x\equiv a^{b-1}\pmod b$$

则进一步有：

$$x\equiv a^{b-2}\pmod b$$

所以我们只需要用快速幂求出$a^{b-2}\bmod b$即可。

//The code is from dxbdly
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
    int x=0;
    char c=getchar();
    bool f=0;
    while (!isdigit(c))
          f=f|(c=='-'),c=getchar();
    while (isdigit(c))
          x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return f?-x:x;
}
inline int ksm(int a,int b,int p)
{
    int res=1;
    while (b)
          {
          if (b&1)
             res=res*a%p;
          a=a*a%p,b>>=1;
          }
    return res%p;
}
int main(){
    int a,b;
    a=read(),b=read();
    printf("%d",ksm(a,b-2,b))
    return 0;
}

$3^o$ 求多个连续逆元

题面

考虑如何线性求$i\in[1,n]$，$\bmod b$意义下的逆元。

首先要知道，$1^{-1}\equiv1\pmod b$

我们设$b=i*k+r$，则$k=\frac{b}{i}$，$r=b\bmod i$

把这个式子放到$\bmod b$意义下就可以得到：

$$i*k+r\equiv0\pmod b$$

将其乘上$i^{-1}*r^{-1}$
可得：

$$r^{-1}*k+i^{-1}\equiv0\pmod b$$

即

$$i^{-1}\equiv -k*r^{-1}\pmod b$$

将$k=\frac{b}{i}$与$r=b\bmod i$代入得：

$$i^{-1}\equiv -\lfloor{\frac{b}{i}}\rfloor*(b\bmod i)^{-1}\pmod b$$

而$i^{-1}$就是$i$的逆元，所以可以线性求出。

//The code is from dxbdly
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read()
{
    int x=0;
    char c=getchar();
    bool f=0;
    while (!isdigit(c))
          f=f|(c=='-'),c=getchar();
    while (isdigit(c))
          x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return f?-x:x;
}
int n,p;
int inv[3000005];
signed main(){
    n=read(),p=read();
    inv[1]=1;
    for (register int i=2;i<=n;++i)
        inv[i]=(p-p/i)*inv[p%i]%p;
    for (register int i=1;i<=n;++i)
        printf("%lld\n",inv[i]);
    return 0;
}

4.整除分块

$1^o$ 内容

经典问题：

求$\sum_{i=1}^{n}{\lfloor{\frac{i}{n}}\rfloor}$的值

$(n<=10^9)$

对于此题，我们可以先考虑在不同情况下$\lfloor{\frac{i}{n}}\rfloor$的值

不难发现，$\lfloor{\frac{i}{n}}\rfloor$最多只有$\sqrt{n}$种取值。

可以考虑：将原式根据$\lfloor{\frac{i}{n}}\rfloor$的取值，分成几段求解。

若$i\in{[l,r]}$时$\lfloor{\frac{i}{n}}\rfloor$均相等，则$\sum_{i=l}^{r}{\lfloor{\frac{i}{n}}\rfloor}$很好计算。

即$(n/l)*(r-l+1)$，且计算的时间复杂度在$O(1)$

所以我们可以$O(\sqrt{n})$的枚举块，对于每一个块$O(1)$求解，总时间复杂度$O(\sqrt{n})$

代码如下：

//The code is from dxbdly
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read()
{
    int x=0;
    char c=getchar();
    bool f=0;
    while (!isdigit(c))
          f=f|(c=='-'),c=getchar();
    while (isdigit(c))
          x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return f?-x:x;
}
int n,ans;
signed main(){
    n=read();
    for (register int l=1,r;l<=n;l=r+1)
        r=n/(n/l),ans+=(r-l+1)*(n/l);
    printf("%lld",ans);
    return 0;
}

$2^o$ 例题P2261 [CQOI2007]余数求和

题面

题解：

分析数据范围，显然不能暴力，们先来推式子

由题意：

$$G(i,j)=\sum_{i=1}^{n}{k \bmod i}$$

将$\bmod$运算转化为整除运算：

$$G(i,j)=\sum_{i=1}^{n}{k-\lfloor{\frac{k}{i}}\rfloor}*i$$

整理得

$$G(i,j)=n*k-\sum_{i=1}^{n}{\lfloor{\frac{k}{i}}\rfloor}*i$$

那么我们可以利用整除分块解决。

那么对于
$i\in[l,r]$使得$\lfloor{\frac{k}{i}}\rfloor$相等的公式为

$$(k/l)*(r-l+1)*(l+r)/2$$

AC代码：

//The code is from dxbdly
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read()
{
    int x=0;
    char c=getchar();
    bool f=0;
    while (!isdigit(c))
          f|=(c=='-'),c=getchar();
    while (isdigit(c))
          x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return f?-x:x;
}
int n,k;
int sum;
signed main(){
    n=read(),k=read();
    for (register int l=1,r;l<=n;l=r+1)
        {
        int x=k/l;
        r=(x?min(k/x,n):n);
        sum+=(r-l+1)*(l+r)/2*x;
        }
    printf("%lld",n*k-sum);
    return 0;
}

5. $\phi$函数

定义：

$\phi(n)$的公式

$$\phi(n)=n*\prod_{i=1}^{m}{1-\frac{1}{p_i}}$$

其中$p_i$为$n$的质因数。

可以理解为：

$$\phi(n)=\sum_{i=1}^{n}{\begin{cases} 1, & \text{if $\gcd$(i,n) = 1} \\ 0, & \text{if $\gcd$(i,n)$\neq${1}} \end{cases} }$$

即统计，$1$~$n$中与$n$互质的个数

$\phi(n)$是一个积性函数

$\phi(n)$的求法需要用到线性筛，下一点中会提到。

6.筛法

$1^o$ 埃拉托斯特尼筛法(埃氏筛)

基本算法，不多讲，很简单。

其思想是每次确定一个质数，就将此质数所有倍数排除。

时间复杂度约$O(n^2)$

$2^o$ 欧拉筛(线性筛)

欧拉筛其实就是在埃氏筛上做出了优化，使得时间复杂度成功降到$O(n)$。

考虑埃氏筛的冗余，一个数可能会被多个质数所筛中，从而增大复杂度。

欧拉筛法保证了每个数都只被一个质数筛一遍，算法结束时每个数都要被筛到，所以复杂度为$O(n)$

先放代码：

//The code is from dxbdly
inline void get_prime()
{
    for (register int i=2;i<=n;++i)
        {
        if (!b[i])
           prime[++tot]=i;
        int x=prime[1]*i;
        for (register int j=1;j<=tot&&x<=n;++j,x=prime[j]*i)
            {
            b[x]=1;
            if (!(i%prime[j]))
                break;
            }
        }
}

注意到最后一个$if$语句，那便是防止一个数重复被筛的关键。

$3^o$ 欧拉筛求$\phi(1)$~$\phi(n)$

我们容易得出：

$$\begin{cases} \phi(n)=n-1 & \text{当n为质数} \\ \phi(np)=p*\phi(n) & \text{当p为质数且p$\mid$n}\\ \phi(np)=(p-1)*\phi(n) & \text{当p为质数且p$\nmid$n} \end{cases}$$

那么即可在线性筛时$O(n)$的处理出$\phi(1)$~$\phi(n)$的值

代码：

//The code is from dxbdly
inline void get_phi()
{
    phi[1]=1;
    for (register int i=2;i<=n;++i)
        {
        if (!b[i])
           prime[++tot]=i,phi[i]=i-1;
        int x=prime[1]*i;
        for (register int j=1;j<=tot&&x<=n;++j,x=prime[j]*i)
            {
            b[x]=1;
            if (!(i%prime[j]))
               {
               phi[x]=prime[j]*phi[i];
               break;
               }
            phi[x]=(prime[j]-1)*phi[i];
            }
        }
}

7.费马小定理，欧拉定理，扩展欧拉定理

$1^o$ 内容

费马小定理：

若 $p$ 是一个质数, 且 $a$ 不是 $p$ 的倍数，则有：

$$a^{p-1}\equiv 1\pmod p$$

欧拉定理：

若 $a,p$ 互质，则有：

$$a^{\phi(p)}\equiv1\pmod p$$

拓展欧拉定理：

当 $x≥\phi(p)$，则有 :

$$a^x\equiv a^{x\,mod\,\phi(p)+\phi(p)}\pmod p$$

$2^o$ 例题P4139 上帝与集合的正确用法

题面

题解：

我们令：

$$ans(p)\equiv2^{2^{2^{2^\cdots}}}\pmod p$$

则，套用拓展欧拉定理可得

$$ans(p)=2^{ans(\phi(p))+\phi(p)}\pmod p$$

预处理出$\phi(1)$~$\phi(p)$，递归求解$ans(p)$

递归复杂度$O(\log p)$，预处理复杂度$O(p)$

总复杂度：$O(p+\log p)$可过！

AC代码：

//The code is from dxbdly
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
    int x=0;
    char c=getchar();
    bool f=0;
    while (!isdigit(c))
          f|=(c=='-'),c=getchar();
    while (isdigit(c))
          x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return f?-x:x;
}
int t,p;
int prime[10000005],phi[10000005],tot;
bool b[10000005];
inline void get_phi()
{
    phi[1]=1;
    for (register int i=2;i<=10000000;++i)
        {
        if (!b[i])
           prime[++tot]=i,phi[i]=i-1;
        int x=prime[1]*i;
        for (register int j=1;j<=tot&&x<=10000000;++j,x=prime[j]*i)
            {
            b[x]=1;
            if (!(i%prime[j]))
               {
               phi[x]=prime[j]*phi[i];
               break;
               }
            phi[x]=(prime[j]-1)*phi[i];
            }
        }
}
inline int ksm(int a,int b,int m)
{
    int ans=1;
    while (b)
          {
          if (b&1)
             ans=1ll*ans*a%m;
          a=1ll*a*a%m,b>>=1;
          }
    return ans;
}
inline int get_ans(int x)
{
    if (x<=2) 
       return 0;
    return ksm(2,get_ans(phi[x])+phi[x],x);
}
int main(){
    t=read();
    get_phi();
    while (t--)
          {
          p=read();
          printf("%d\n",get_ans(p));
          }
    return 0;
}

8. 中国剩余定理与拓展中国剩余定理

注：部分引用自博客

$1^o$ 中国剩余定理（CRT）

问题：

求同余方程组：

$$\begin{cases} x\equiv{a_1}\pmod{b_1} \\ x\equiv{a_2}\pmod{b_2}\\ x\equiv{a_3}\pmod{b_3}\\ \cdots\\ x\equiv{a_n}\pmod{b_n} \end{cases}$$

其中$b_1,b_2,b_3,\cdots,b_n$为两两互质的整数。

求$x$的最小非负整数解。

令：$M=\prod_{i=1}^{n}{b[i]}$

令：$t_i$为同余方程$\frac{M}{b_i}*t_i\equiv1\pmod{b_i}$

则，一定有一个解

$$x=\sum_{i=1}^{n}{a_i*t_i*\frac{M}{b_i}}$$

且，其最小非负整数解为：

$$x=(x\bmod M+M)\bmod M$$

代码：

//The code is from dxbdly
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
    int x=0;
    char c=getchar();
    bool f=0;
    while (!isdigit(c))
          f=f|(c=='-'),c=getchar();
    while (isdigit(c))
          x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return f?-x:x;
}
int n;
int a[100005],b[100005],x,y;
inline void exgcd(int a,int b)
{
    if (b==0)
       {
       x=1,y=0;
       return ;    
       }
    exgcd(b,a%b);
    int x0=x,y0=y;
    x=y0,y=x0-a/b*y0;
}
inline void work()
{
    int lcm=1,ans=0;
    for (register int i=1;i<=n;++i)
        lcm*=b[i];
    for (register int i=1;i<=n;++i)
        {
        int cnt=lcm/b[i];
        exgcd(cnt,b[i]);
        x=(x%b[i]+b[i])%b[i];
        ans=(ans+a[i]*x*cnt)%lcm;
        }
    printf("%d",(ans%lcm+lcm)%lcm);
}
int main(){
    n=read();
    for (register int i=1;i<=n;++i)
        a[i]=read();
    for (register int i=1;i<=n;++i)
        b[i]=read();
    work();
    return 0;
}

$2^o$ 例题P3868 [TJOI2009]猜数字

题面

题解：

由题意得：

$$\begin{cases} b_1\mid n-a_1 \\ b_2\mid n-a_2\\ \cdots\\ b_k\mid n-a_k) \end{cases}$$

化为同余式：

$$\begin{cases} n*a_1\equiv0\pmod{b_1} \\ n*a_2\equiv0\pmod{b_2}\\ \cdots\\ n*a_k\equiv0\pmod{b_k} \end{cases}$$

整理：

$$\begin{cases} n\equiv{a_1}\pmod{b_1}\\ n\equiv{a_2}\pmod{b_2}\\ \cdots\\ n\equiv{a_k}\pmod{b_k} \end{cases}$$

直接套用中国剩余定理即可。

//The code is from dxbdly
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read()
{
    int x=0;
    char c=getchar();
    bool f=0;
    while (!isdigit(c))
          f=f|(c=='-'),c=getchar();
    while (isdigit(c))
          x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return f?-x:x;
}
int n;
int a[15],b[15];
int x,y;
inline int mul(int a,int b,int m)//此题需要用快速乘法加速
{
    int ans=0;
    while (b)
          {
          if (b&1)
             ans=(ans+a)%m;
          a=(a<<1)%m,b>>=1;
          }
    return ans;
}
inline void exgcd(int a,int b)
{
    if (b==0)
       {
       x=1,y=0;
       return ;
       }
    exgcd(b,a%b);
    int x0=x,y0=y;
    x=y0,y=x0-a/b*y0;
}
inline int work()
{
    int lcm=1,ans=0;
    for (register int i=1;i<=n;++i)
        lcm*=b[i];
    for (register int i=1;i<=n;++i)
        {
        int cnt=lcm/b[i];
        exgcd(cnt,b[i]);
        x=(x%b[i]+b[i])%b[i];
        ans=(ans+mul(mul(a[i],x,lcm),cnt,lcm))%lcm;
        }
    printf("%lld",(ans%lcm+lcm)%lcm);
}
signed main(){
    n=read();
    for (register int i=1;i<=n;++i)
        a[i]=read();
    for (register int i=1;i<=n;++i)
        b[i]=read();
    for (register int i=1;i<=n;++i)
        a[i]=(a[i]%b[i]+b[i])%b[i];
    work();
    return 0;
}

$3^o$ 拓展中国剩余定理(EXCRT）

题面

假设已经求出前$n-1$个方程组成的同余方程组的一个解为$x$

令：$M=\prod_{i=1}^{n-1}{b[i]}$

则前$n-1$个方程的通解为：

$$x=x+i*M$$

那么加入第n个式子，则问题变为：

求一个正整数$t$使得

$$x+t*M\equiv{a_n}\pmod{b_n}$$

整理得：

$$t*M\equiv{a_n-x}\pmod{b_n}$$

而此式子可以通过拓展欧几里得求解。

那么我们就能求出前$n$个式子的一个解：

$$x_n=x+M*t$$

同理处理前$n-1$个式子，所以只要跑$n$遍拓展欧几里得即可！

//The code is from dxbdly
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read()
{
    int x=0;
    char c=getchar();
    bool f=0;
    while (!isdigit(c))
          f=f|(c=='-'),c=getchar();
    while (isdigit(c))
          x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return f?-x:x;
}
int n;
int a[100005],b[100005];
int x,y;
inline int mul(int a,int b,int m)
{
    int ans=0;
    while (b)
          {
          if (b&1)
             ans=(ans+a)%m;
          a=(a<<1)%m,b>>=1;
          }
    return ans;
}
inline int exgcd(int a,int b)
{
    if (!b)
       {
       x=1,y=0;
       return a;
       }
    int gcd=exgcd(b,a%b);
    int x0=x,y0=y;
    x=y0,y=x0-a/b*y0;
    return gcd;
}
inline void work()
{
    int lcm=b[1],ans=a[1];
    for (register int i=2;i<=n;++i)
        {
        int cnt=(a[i]-ans%b[i]+b[i])%b[i],gcd=exgcd(lcm,b[i]),mod=b[i]/gcd;
        x=mul(x,cnt/gcd,mod);
        ans=ans+lcm*x,lcm*=mod;
        ans=(ans%lcm+lcm)%lcm;
        }
    printf("%lld",(ans%lcm+lcm)%lcm);
}
signed main(){
    n=read();
    for (register int i=1;i<=n;++i)
        b[i]=read(),a[i]=read();//注意是倒着读的。
    work();
    return 0;
}