同余：欧拉定理及扩展定理，费马小定理

在一些计数的问题中，常常要求对结果取模，但是在计算非常庞大的次幂的时候，无法直接取模，可以先把底数对 p 取模，指数对$ \varphi(p)$ 取模，再计算次幂，有效地降低时间复杂度。

第二章 同余

0x20 同余

0x21 整数的取余运算

0x21.1 整数的取余运算（模运算）

定义：带余除法，设 a , b 是整数，且 b > 0，使得 a=bq+r，且 0≤r<b ，称 q 为商， r 为余数。

显然带余除法中的商和余数都是唯一的，在下文中将商记为 a / b ，将余数记为 a % b ，/ 与 % 的运算优先级与乘除法相同。

• 定义以下运算：

取模运算：a % p (或a mod p)，表示 a 除以 p 的余数。
模 p 加法：(a+b)%p ，其结果是a + b 算术和除以p的余数，也就是说，( a + b ) = k p + r ，则( a + b ) % p = r 。
模 p 减法：( a − b ) % p，其结果是a − b算术差除以p的余数。
模 p 乘法：( a ∗ b ) % p，其结果是a ∗ b 算术乘法除以p的余数。

• 模运算有如下简单性质：

$a \% b = a-b\times \lfloor\frac{a}{b}\rfloor$，即若 a % b = c ，则 a = b x + c ，$x= \lfloor\frac{a}{b}\rfloor$。

n % p 得到结果的正负由被除数 n 决定,与 p 无关。

结合率：

$((a+b) \% p + c) \% p = (a + (b+c) \% p) \% p$

$((a\times b) \% p\times c)\% p = (a\times (b\times c) \% p) \% p$

交换率：

$(a + b) \% p = (b+a) \% p$

$(a\times b) \% p = (b\times a) \% p$

分配率：

$((a +b)\% p\times c) \% p = ((a \times c) \% p + (b\times c) \% p) \% p$

若$a\%p=x,a\%q=x,\gcd(p,q)=1$，则$a\%(p×q)=x$

更多关于模运算性质以及同余详见本文 0x22同余。

0x21.2 整数模意义下的加减乘乘方运算

$(a+b) \%c=(a\%c+b\%c)\%c$
$(a-b)\%c=(a\%c-b\%c+c)\%c$
$(a \times b)\%c=(a\%c)\times (b\%c)\%c$
$(a^b) \% p = ((a \% p)^b) \% p$
计算减法的时候，通常需要加上模数 c，防止出现负数。

$O(nlogn)$ 的 大数快速幂算法

#include <bits/stdc++.h>
#define int long long
using namespace std;
int mod;
char s[20000001];
int qqpow(int a, int b)
{
    int ret=1;
    while(b)
    {
        if(b&1)ret=(ret*a)%mod;
        a=(a*a)%mod;
        b>>=1;
    }
    return ret;
} 
int qpow(int a, char *b, int len)
{
    int ret=1;
    while(len>0)
    {
        if(b[len-1]!='0')
             ret=(ret*qqpow(a,b[len-1]-'0'))%mod;
        a=(qqpow(a,10))%mod;
        len--;
    }
    return ret;
}
int read(char s[])
{
    int len=0;
    char ch;
    while((ch=getchar())!='\n')
    {
        s[len++]=ch;
    }
    return len;
}
signed main()
{

    int a;
    scanf("%lld %lld",&a,&mod);
    getchar();
    int len;
    len=read(s);
    cout<<qpow(a,s,len);
    return 0;
}

对应题目改编自洛谷

【模板】扩展欧拉定理

题目背景

出题人也想写有趣的题面，可惜并没有能力。

题目描述

给你三个正整数，$a,m,b$，你需要求：$a^b \bmod m$

输入格式

一行三个整数，$a,m,b$

输出格式

一个整数表示答案

样例 #1

样例输入 #1

2 7 4

样例输出 #1

2

样例 #2

样例输入 #2

998244353 12345 98765472103312450233333333333

样例输出 #2

5333

提示

注意输入格式，$a,m,b$ 依次代表的是底数、模数和次数

【样例 $1$ 解释】
$2^4 \bmod 7 = 2$

【数据范围】
对于 $100\%$ 的数据，$1\le a \le 10^9$，$1\le b \le 20000000，1\le m \le 10^8$。

改了什么捏，当然是把b的数据范围改了。嘻嘻

那就可以过了

然而原题的数据范围是$1≤b≤10^{20000000}$

0x22 同余

若正整数 a 和 b 除以 m 的余数相等，则称 a ，b 模 m 同余，记作$a\equiv b\ (\text{mod}\ m)$。

即 a % m = b % m

0x21.1 同余的性质

同余的基本性质：

性质21.1.1 ： (自反性)：$a≡a(mod m)$

性质21.1.2 ： (对称性)：$若 a≡b(\mod\ m)，则 b≡a(\mod\ m)$

性质21.1.3 ： (传递性)：$若 a≡b(\mod\ m),b≡c(\mod\ m)，则 a≡c(mod m)$

性质21.1.4 ： (同加性)：$若 a≡b(mod m)，则 a±c≡b±c(mod m)$

性质21.1.5 ： (同乘性)：

$若 a≡b(\mod \ m)，则 a×c≡b×c(\mod\ m)$，$若 a≡b(\mod\ m),c≡d(\mod\ m)，则 a×c≡b×d(\mod\ m)$

性质21.1.6 ： (同幂性)：$a^c≡b^c(\mod\ m)$

性质21.1.7 ： (不满足同除性)：若 $a≡b(mod m)$不满足$a÷c≡b÷c(mod m)$

性质21.1.8 ： (满足同除性)：

若$a≡b(mod m)$，$c ∣ a ， c ∣ b$ , 则 $\cfrac{a}{c}≡\cfrac{b}{c}\ \pmod {\cfrac{m}{\gcd(m,c)} } $

或者可以换一种表述方式： 若 $ca≡cb (\mod m)$则 $a≡b \pmod {\frac{m}{\gcd(m,c)} }$

例如：$\gcd(c,m)=1\Longrightarrow a\equiv b\pmod m$

该性质会在取遍剩余系会用到。

推论21.1.9 ：若$ a≡b(modm) ， m’\ |\ m$， 则$a≡b \pmod {m’}$

推论21.1.10 ：

$a≡b \pmod {m_i} (i=1..k)$等价于 $a≡b \pmod M =\mathrm{lcm}(m1,m2,..mk)$

推论21.1.12 ：$a≡b(modm)$ 且 $c≡d(modm)$ $\Longrightarrow a+c\equiv b+d\pmod m$
推论21.1.13 ：$a≡b(modm) $且 $c≡d(modm) \Longrightarrow a-c\equiv b-d\pmod m$

0x21.2 费马小定理

若 p 是质数，则对于任意的整数 a 都有$a^p≡a \pmod p$。若 $gcd(a,p)=1 $，即 a 不是 p 的倍数，则有 $a^{p−1}≡1\pmod p$

费马小定理降幂：$a^k\equiv a^{k\mod(p-1)}\;(\mod \;p)$

费马大定理：

m > 2 时， $x^m + y^m = z^m$无正整数解
当m = 2 ，对于式子 $a^2+b^2=c^2$
（n 为任意正整数）：
当 a 为奇数时：$a=2n+1,c=n^2+(n+1)^2,b=c-1$
当 a 为偶数时：$a=2n+2,c=1+(n-1)^2,b=c-2$

0x21.3 欧拉定理

欧拉定理
定理21.3.1 ： 若正整数 a , n 互质，则 $a^{\varphi(n)}≡1(\mod\ n) $其中$ \varphi(n)$是欧拉函数。
推论21.3.2： $\exists x\in N^{*},a^x\equiv 1(\mod m) \iff \gcd(a,m)=1$

欧拉降幂（拓展欧拉定理）
若 a 与 m 互质：
$a^b\equiv a^{b\mod\varphi(m)}\pmod m$

若不保证 a 与 m 互质：$b> \varphi(m) 时：a^b\equiv a^{b\mod \varphi(m)+\varphi(m)}\;\pmod m$

在一些计数的问题中，常常要求对结果取模，但是在计算非常庞大的次幂的时候，无法直接取模，可以先把底数对 p 取模，指数对 $\varphi(p)$取模，再计算次幂，有效地降低时间复杂度。

欧拉函数的性质

0x14 互质与欧拉函数
0x14.1 欧拉函数
定义: ∀a,b∈N 若$ gcd ⁡ ( a , b ) = 1 ,$则称 a , b 互质。

• 对于三个数或更多的数，把gcd ⁡ ( a , b , c ) = 1称之为 a , b , c 互质。

• 把 $gcd ⁡ ( a , b ) = gcd ⁡ ( a , c ) = gcd ⁡ ( b , c ) = 1$称之为 a , b , c 两两互质。显然 a , b , c 两两互质是优于 a , b , c 互质的。

性质14.1.1：int 范围内的数 n 中， $1\sim n$中与 n 互质的个数最多只有$1600（\quad max ⁡ \{ φ ( 1 ∼ 2147483647 ) \}\quad )$

欧拉函数

• 定义：1 ⋯ N中与 N 互质的数的个数，被称为欧拉函数，记作 $\varphi(N)$，phi。

  • 如果 n 是一个素数，那么 $φ(n)=n−1$ （所有小于 n 的都互素）

  • 如果 n 是素数的 k 次幂，即$n = p^k$，那么 $φ(p^k) = p^k - p^{k-1}$（除了 p的倍数以外，与 1 ∼ n 中的任意数都互素）

我们可以的到下列结论：

由算数基本定理（唯一分解定理）得

$$N= p_{1}^{k_{1}} \times p_{2}^{k_{2}} \times p_{3}^{k_{3}} \times \cdots \ p_{m}^{k_{m}}$$

则有：

$$\varphi(N)=N \times \prod_{p\mid N}(1-\frac{1}{p})$$

其中，如果 p是素数,则$φ( p) =p\times (1- \frac{1}{p}) = p-1$

我们可以利用这个性质在分解质因数的同时 $ O(\sqrt n)$使用公式求解欧拉函数

inline int euler_one(int n)
{
    int ans = n;
    for(int i = 2;  i * i <= n; ++ i){
        if(n % i == 0){
            ans = ans / i * (i - 1);
            while(n % i == 0)n /= i;
        }
    }
    if(n > 1)ans = ans / n * (n - 1);
    return ans;
}

由此我们得到了上面那道题的真实数据范围条件$（1≤b≤10^{20000000}）$下的$a^b\mod m$的代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;
int mod;
string s;
int qmul(int x,int y,int mod)
{
    int z=(long double)x/mod*y;
    int res=(unsigned long long)x*y-(unsigned long long)z*mod;
    return (res+mod)%mod;
}
int qpow(int a,int b,int mod)
{
    int ans=1;
    while(b)
    {
        if(b&1)ans=qmul(ans,a,mod);
        a=qmul(a,a,mod);
        b>>=1;
    }
    return ans;
}
int varphi(int n)//求varphi(n)
{
    if(n==1)return 1;
    int ans=n;
    for(int i=2;i*i<=n;i++)
    {
        if(n%i==0)
        {
            ans=ans/i*(i-1);
            while(n%i==0)n/=i;
        }
    }
    if(n>1)//n 此时为 超过 输入时的n开根号  的唯一一个质数
//比如n=21，n经过前面了这里变成7        
    ans=ans/n*(n-1);
    return ans;
}
void EEt(int a,string b,int mod)
{
    int b_mod=0;
    int tmod=varphi(mod);//!
    //cout<<tmod<<endl;
    for(int i=0;i<b.length();i++)
    {
        b_mod=b_mod*10+b[i]-'0';
        if(b_mod>=tmod)
        {
            b_mod%=tmod;
        }
    }
    //cout<<b_mod<<endl;
    int bb=0;
    //cout<<"tmod"<<tmod<<endl;
    if(b.length()<=10)bb=stol(b,nullptr,10);
    //cout<<bb<<"bb"<<endl;
    if(bb!=0 && bb<=tmod){printf("%lld",qpow(a,bb,mod));}
    else
    {
        b_mod = b_mod + tmod;
        printf("%lld", qpow(a, b_mod, mod));
        return;
    }
}    
signed main()
{

    int a;
    scanf("%lld %lld",&a,&mod);
    getchar();
    cin>>s;
    EEt(a,s,mod);
    return 0;
}

0x51.1 线性筛法求欧拉函数
我们注意到在线性筛中，每一个合数都是被最小的质因子筛掉，筛法求素数的同时也得到了每个数的最小质因子，这是线性筛求欧拉函数的关键。

1.考虑$n=p^k_j,\varphi(n)$

显然有$\varphi(p^k_j)=p^k_j-p^{k-1}_j=p_j^{k-1}\times(p_j-1)$

2.考虑$n=i\times p_j$当$p_j\mid i$

即$i$含有因子$p_j$,由于$i=\frac{n}{p_j}$，由唯一分解定理：

$$\begin{aligned} \varphi(n) & =n\times \prod_{i=1}^{s}\frac{p_i-1}{p_i} \\[2ex] & =p_1\times i\times \prod_{i=1}^{s}\frac{p_i-1}{p_i} \\[2ex] & =p_1\times \varphi(i) \end{aligned}$$

3.考虑 $n=i\times p_j$，$\varphi(n)$，当 $i$ 不整除$p_j$

即 $i$ 与 $p_j$ 互质，积性函数显然有性质：

$$\varphi(n)=\varphi(i)\times \varphi(p_j)=\varphi(i)\times(p_j-1)$$

由于我们仅在在线性筛的框架上增加了一些细节，所以时间复杂度依然是O(n)的。

威尔逊定理：解决带有“！”的问题

0x21.4 威尔逊定理
威尔逊定理

定理21.4.1： 当 p 为质数时有：

$(p-1)!\equiv p-1\equiv -1(\mod\;p)$，

$(p-2)!\equiv 1\pmod p$

其中 定理21.4.1 实际上就等价于：若 p 是质数，则 (p−1)!+1 能够被 p 整除。
n 为素数时： $(n-1)!\mod n=1$
n 为合数时：除 n = 4 以外，$(n-1)!\mod n=0$

• 威尔逊定理的逆命题

定理21.4.2： 若一个数 p，满足条件$(p−1)!+1$可以被 p 整除，那么 p 是素数。

即：p 可整除 (p-1)!+1 是 p 为质数的充要条件。

• $例题：杭州电子科技大学HDU$

Problem B. Fansblog（HDU 6608 19多校）

给定一个质数$P(10^9≤P≤10^{14})$， Q 是 最大的那个小于 P 的质数，求 $Q\ !\ \%P$

Solution

根据威尔逊定理 $(P-1)!\equiv P-1\equiv -1(\mod P)$，所以显然可以构造答案 Q !

我们知道P>Q，则有$(P-1)!\equiv1\times 2\times······\times Q \times (Q+1)\times······\times (P-1)\equiv P-1(\mod P)$

则有：$Q!\equiv\cfrac{P-1}{(Q+1)\times······\times (P-1)}\equiv\cfrac{1}{(Q+1)\times······\times (P-2)}(\mod P)$

即求$(Q+1)\times······\times (P-2)$的逆元，当然目前还不会求