num>>i 表示将 \(num\) 的二进制表示向右移动1位所得的值。

注意：+ 和-的优先级高于左移右移

高精度

#include
#include
#include
#include
#include
#define base 100000
#define cut 5
#define L 10000
using namespace std;

struct Big{
    int len;
    long long num[L];
    Big(){
        len=1;
        memset(num,0,sizeof(num));
    }
    Big operator=(const Big &a){
        len=a.len;
        for(int i=0;i>(istream&,Big&);
    friend ostream&operator<<(ostream&,Big&);
};

int operator>(const Big a,const Big b){
    if(a.len!=b.len){
        if(a.len>b.len) return 1;
        return 0;
    }
    for(int i=a.len-1;i>=0;i--)
	    if(a[i]>b[i]) return 1;
    return 0;
}

int operator==(const Big a,const Big b){
    if(a.len!=b.len) return 0;
    for(int i=0;ib || a==b)return 0;
    return 1;
}

Big operator+(Big a,Big b){
    Big ret;
    long long carry=0;
    for(int i=0;;i++){
        ret[i]=a[i]+b[i]+carry;
        carry=ret[i]/base;
        ret[i]%=base;
        if(i>=a.len&&i>=b.len&&carry==0)
         break;
    }
    ret.len=min(L,max(a.len,b.len)+10);
    while(ret.len>0&&ret[ret.len-1]==0)
     ret.len--;
    if(ret.len==0)
     ret.len=1;
    return ret;
}

Big operator+(Big a,int b){
    long long carry=b;
    for(int i=0;;i++){
        a[i]+=carry;
        carry=a[i]/base;
        a[i]%=base;
        if(a[i]==0 && carry==0 && i>=a.len)
         break;
    }
    a.len=min(L,a.len+10);
    while(a.len>0 && a[a.len-1]==0) a.len--;
    return a;
}

Big operator*(Big a,Big b){
    Big ret;
    for(int i=0;i=a.len+b.len-1) break;
    }
    a.len=min(L,a.len+b.len+10);
    while(a.len>0 && a[a.len-1]==0) a.len--;
    return a;
}

Big operator*(Big a,int b){
    long long carry=0;
    for(int i=0;;i++){
        carry+=a[i]*b;
        a[i]=carry%base;
        carry/=base;
        if(carry==0&&a[i]==0&&i>=a.len) break;
    }
    a.len=min(L,a.len+10);
    while(a.len>0&&a[a.len-1]==0) a.len--;
    return a;
}

Big operator-(Big a,Big b){
    long long carry=0;
    for(int i=0;;i++){
        a[i]-=b[i]+carry;
        if(a[i]<0) carry=(-a[i]/base+1);
        else carry=0;
        a[i]+=carry*base;
        if(carry==0&&i>=b.len) break;
    }
    while(a.len>0&&a[a.len-1]==0) a.len--;
    return a;
}

Big operator-(Big a,int b){
    long long carry=b;
    for(int i=0;;i++){
        a[i]-=carry;
        if(a[i]<0) carry=(-a[i]/base+1);
        else carry=0;
        a[i]+=carry*base;
        if(carry==0) break;
    }
    while(a.len>0 && a[a.len-1]==0) a.len--;
    return a;
}

Big operator/(Big a,int b){
     long long carry=0;
     for(int i=a.len-1;i>=0;i--){
         a[i]+=carry*base;
         carry=a[i]%b;
         a[i]/=b;
     }
     while(a.len>0&&a[a.len-1]==0) a.len--;
     return a;
}

Big operator%(const Big a,int b){
     return a-(a/b)*b;
}

int main(){
    return 0;
}

数论

整除性质

性质:

同余性质

最大公约数与最小公倍数

若干个数所有约数中的共同的最大数是最大公约数，倍数中共同的最小数是最小公倍数

一般两个数的最大公约数是 \(\gcd\) 最小公倍数是 \(\mathrm{lcm}\)

\(\gcd(a,b)*\mathrm{lcm}(a,b)=a*b\)

求法：辗转相除

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

整除分块

整除分块是用于快速处理形似

的式子的办法

引理1

证明略

引理2

对于一个较大的 \(n\) 我们显然会发现，我们后面的这个下取整取值并不是每一次都随着 \(i\) 而变化的，它是呈块状分布的，同时这个下取整的值我们也能得到，应该是共有 \(2\sqrt n\) 个值

结论：

通过严谨的数学推理(打表) 我们发现实际上这些取值是有规律的，即

如果一个块的开始位置时 \(l\) 那么它的结束位置 \(r\) 就是 \(\lfloor \dfrac n {\lfloor \frac n l \rfloor} \rfloor\)

那么我们写程序的基本结构就很显然了

for(int l=1,r;l<=n;l=r+1) r=n/(n/l);

所以我们对于形如：

可以对 \(f(i)\) 可以直接前缀和预处理，就可以解决这道问题了

欧拉函数

\(φ(n)\) :定义：1~n中与n互质的数的个数

公式：

莫比乌斯函数

我们一般表示为 \(\mu(x)\)

1. \(\exists d_i\ge 2\)，\(\mu(x)=0\)
2. \(\forall d_i=1\)，\(\mu(x)=(-1)^k\) (\(k\) 是质因数分解后有几项)
3. \(x=1\) ，\(\mu(x)=1\)

如：

\(\mu(6)=1\) \(\mu(7)=-1\) \(\mu(8)=0\)

设 \(s(n)=\sum_{i=d\mid n}^{n} \mu (i)\)

如 \(s(6) = \mu(1) +\mu(2) +\mu(3) +\mu(6)\)

那么：

1. 当 \(n=1\)，\(s(n)=1\)
2. 当 \(n>1\)，\(s(n)=0\)

对于2的证明：

首先我们对于 \(n\) 因式分解：\(n=p_1^{\alpha_1}\times p_2^{\alpha_2}\times\dots\times p_k^{\alpha_k}\) (\(k\ge 1\))

那么我们的每一个 \(d\) 都有：\(d=p_1^{\beta_1}\times p_2^{\beta_2}\times\dots\times p_k^{\beta_k}\) (\(\forall i \in [1,k]\) \(0\le\beta_i\le \alpha_i\))

那么我们算一下 \(\mu(d)\) 可知，我们只需要考虑，如果\(\exists i \in [1,k]\)，\(\beta_i\ge 2\) 则原式为0

所以我们只需要看里面有多少个1即可

所以我们用组合数算一下：

我们这时候看一下二项式定理：

钦定 \(a=1\) \(b=-1\)

所以 \(\mu(x)\) 必然等于=0，得证

各种筛法

埃氏筛

用于统计从1-n中的质数

原理：从前往后筛，如果筛到一个数\(i\)，然后把\(i\)的倍数都删了

时间复杂度：\(O(nlog^2n)\) 基本可以跑到3e5

void statistics(int n){
    for(int i=2;i<=n;i++){
        if(!st[i]) prime[++k]=i;
        for(int j=1;prime[j]*i<=n;j++){
            st[prime[j]*i]=true;
        }
    }
}

线性筛

这个东西很重要，关系到后面的积性函数求解

先放一个代码：

void primes(int n){
    for(int i=2;i<=n;i++){
        if(!st[i]) prime[++k]=i;
        for(int j=1;prime[j]*i<=n;j++){
            st[i*prime[j]]=true;
            if(!(i%prime[j])) break;
        }
    }
}

我们观察和上面那个的区别

发现无非就是多了一行if(i%prime[j]==0) break;

我们先给个证明来说明这句话加上后的正确性

证明

当\(i\)是\(prime[j]\)的整数倍时\(\iff prime[j]\mid i\)

设 \(k=i/prime[j]\)

则 \(i*prime[j+1]=prime[j]*(prime[j+1]*k)\)

所以说 \(i*prime[j]\) 是 \(prime[j]\) 的整数倍

不需要继续标记

对于 \(prime[j+2]*i\) 等同理，所以说可以直接跳出循环，不需要重新标记

这样线性筛的复杂度就可以被优化到 \(O(n)\) 了

欧拉筛

我们可以把这件求phi分成两步

k是质数

首先我们容易发现一个问题：如果\(k\)是质数，那么\(\varphi (k)\)显然等于\(k-1\)，因为小于\(k\)的数都与\(k\)互质

所以我们可以把这一句：if(!vis[i]) p[++num]=i;再加上一句phi[i]=i-1;

1. \(i\%p=0\) 时

   然后我们需要证明一个东西：

   若\(p\mid i\)且\(p\)为质数 则 \(\varphi(i*p)\)=\(p*\varphi(i)\)

   证明：

   若\(p \mid i\) 则可以推出\(p\) 是 \(i\) 的一个质因子

   我们发现：一个数的欧拉函数与每一项的次数无关

   所以说

   \[\varphi(i*p)=i*p*(1-\frac{1}{p_1})*(1-\frac{1}{p_2})...*(1-\frac{1}{p_k}) \]

   同时

   \[\varphi(i)=i*(1-\frac{1}{p_1})*(1-\frac{1}{p_2})...*(1-\frac{1}{p_k}) \]

   发现两个式子除了 \(i*p\) 全部相同

   所以我们可以推出 \(\varphi(i*p)\)=\(p*\varphi(i)\)

   证毕

   那么很显然在这一句中if(i%prime[j]==0) break;我们可以加上phi[prime[j]*i]=prime[j]*phi[i]

2. \(i\%p!=0\) 时

   \(p\) 一定是 \(i*p_j\) 的最小质因子

   先把 \(\varphi(i)\) 的式子摆在这

   \[\varphi(i)=i*(1-\frac{1}{p_1})*(1-\frac{1}{p_2})...*(1-\frac{1}{p_k}) \]

   然后

   \[\varphi(p*i)=p*i*(1-\frac{1}{p_1})*(1-\frac{1}{p_2})...*(1-\frac{1}{p_k}*(1-\frac{1}{p})) \]

   我们把下面的式子除以上面的式子发现：

   \[\varphi(p*i)/\varphi(i)=p*(1-\frac{1}{p})=p-1 \]

   把 \(\varphi(i)\) 挪到右边最后可以得到

   \[\varphi(p*i)=\varphi(i)*(p-1) \]

   所以我们讨论完了所有的情况，可以得到最终式子：

inline void get_euler(int n){
    phi[1]=1;
    for(int i=2;i<=n;i++){
        if(!st[i]){
            phi[i]=i-1;
            prime[++cnt]=i;
        }
        for(int j=1;prime[j]*i<=n && j<=cnt;j++){
            st[prime[j]*i]=true;
            if(i%prime[j]==0){
                phi[i*prime[j]]=prime[j]*phi[i];
                break;
            }
            phi[i*prime[j]]=phi[i]*(prime[j]-1);
        }
    }
}

莫比乌斯筛

这个比较简单，就不写了

inline void get_euler(int n){
    phi[1]=1;
    for(int i=2;i<=n;i++){
        if(!st[i]){
            mu[i]=-
            phi[i]=i-1;
            prime[++cnt]=i;
        }
        for(int j=1;prime[j]*i<=n && j<=cnt;j++){
            st[prime[j]*i]=true;
            if(i%prime[j]==0){
                phi[i*prime[j]]=prime[j]*phi[i];
                break;
            }
            mu[i*prime[j]]=-mu[i];
            phi[i*prime[j]]=phi[i]*(prime[j]-1);
        }
    }
}

分解质因数

试除法

用于单个数检验是否为质数

原理：从1枚举到\(\sqrt n\)观察是否有数能被n整除

void prime(int x){
    int n=x;
    for(int i=2;i*i<=n;i++){
        if(x%i==0) 
            while(n%i==0) 
                vec[x].push_back(i),n/=i;
    }
    if(n) vec[x].push_back(n);
}

Miller-Rabin

用法：\(O(k\log^2n)\) 判断 \(n\) 是否是质数。其中 \(k\) 是枚举底数的个数，\(2^{78}\) 以内只需要枚举 \(12\) 个。

费马小定理：

若 \(p\) 是质数且 \(p \nmid a\)

我们可以根据费马小定理得出一种检验素数的思路(Fermat 素性测试)：

它的基本思想是不断地选取在 \([2,n)\) 中的 \(a\)，并检验是否每次都有 \(a^{n?1}\equiv 1 \pmod n\)

但是很遗憾，费马小定理的逆定理并不成立

卡迈克尔数：如果有一个合数 \(n\) 满足任何一个 \(a\) 都满足 \(a^{n?1}\equiv 1 \pmod n\)，那么我们称这个合数 \(n\) 为卡迈克尔数，同时，满足 \(m=2^n-1\) 那么 \(m\) 还是卡迈克尔数，所以卡迈克尔数是无穷的

二次探测定理：

若 \(p\) 是奇素数，则 \(x^2 \equiv 1 \pmod p\) 的解为 \(x=1\) 或 \(x=p-1\) \(\pmod p\)

算法流程：

（1）对于偶数和 0，1，2 可以直接判断。

（2）设要测试的数为 \(x\)，我们取一个较小的质数 \(a\)，设 \(s,t\)，满足\(2^s\times t=x-1\) （其中 \(t\) 是奇数）。

（3）我们先算出 \(a^t\)，然后不断地平方并且进行二次探测（进行 \(s\) 次）。

（4）最后我们根据费马小定律，如果最后 \(a^{x-1}\not\equiv 1 \pmod x\)，则说明 \(x\) 为合数。

（5）多次取不同的 \(a\) 进行 \(Miller-Rabin\) 素数测试，这样可以使正确性更高

备注：

（1）我们可以多选择几个 \(a\)，如果全部通过，那么 \(x\) 大概率是质数。

（2）\(Miller-Rabin\) 素数测试中，“大概率”意味着概率非常大，基本上可以放心使用。

（3）当 \(a\) 取前12个素数时，可以证明 \(2^{78}\) 范围内的数不会出错。

（5）另外，如果是求一个 \(\text{long long}\) 类型的平方，可能会爆掉，因此有时我们要用快速乘，不能直接乘。

\(\text{Pollard-Rho}\) 先咕了

裴蜀定理

对于二元一次方程 \(ax+by=c\)，有整数解的充要条件是 \(\gcd(a,b) \mid c\)。

推论：当 \(ax+by=1\) 时，当且仅当 \(\gcd(a,b)=1\) 时有解。

证明：

设 \(d=\gcd(a,b)\) 则 \(d \mid a,d\mid b\)。由整除的性质 \(\forall x,y\in Z\)，有 \(d \mid (ax+by)。\)

设 \(s\) 为 \(ax+by\) 最小正值，令 \(q=\left\lfloor \dfrac{a}{s} \right\rfloor\)。

则 \(r=a\pmod s=a-q(ax+by)=a(1-qx)+b(-qy)\)。

可见 \(r\) 也为的线性组合。

由于 \(r\) 为 \(a\pmod s\) 所得，所以 \(0\leq r。

由于 \(s\) 为线性组合的最小正值,可知。

1. 因此有 $ s\mid a$ ，同理 \(s\mid b\) ，因此，\(s\) 是 \(a\) 与 \(b\) 的公约数，所以 \(d\ge s\)。

   因为 \(d\mid a\) ，\(d\mid b\) ，且 \(s\) 是 \(a\) 与 \(b\) 的一个线性组合，所以由整除性质知 \(d\mid s\)。

2. 但由于 \(d\mid s\) 和 \(s>0\)，因此 \(d\le s\)。

由 1,2 得 \(d=s\) ，命题得证。

exgcd

现在我们对于 \(ax+by=c\) 想要获得一组整数解。

首先 \(c\) 肯定是要满足 \(\gcd(a,b) \mid c\) 的（要不然裴蜀定理白证明了）。

然后我们可以直接求 \(a_1x+b_1y=\gcd(a_1,b_1)\) 的一组整数解，最后 \(x,y\) 再乘上 \(c/\gcd(a_1,b_1)\) 即可

好了，我们现在说怎么求解。

当 \(b=0\) 时，显然 \(x=1,y=0\)

当 \(b\not= 0\) 时，有：

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

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

\(\therefore a x + b y = \gcd ( a , b ) = \gcd ( b , a \bmod b ) = b \times t x + ( a \bmod b ) \times t y\)

\(\because a \bmod b=a- \left\lfloor \dfrac{a}{b} \right\rfloor\times b\)

\(\therefore a x+b y=b\times tx+(a- \left\lfloor \dfrac{a}{b} \right\rfloor\times b)\times ty=a\times ty+b\times(tx?\left\lfloor \dfrac{a}{b} \right\rfloor\times ty)\)

\(\therefore x=ty,y=tx-\left\lfloor \dfrac{a}{b} \right\rfloor\times ty\)

此时我们容易发现： \(x\) 和 \(y\) 都被转化成了两个更小的数，然后递归求解即可

#include
#include
#include
#include
#define ll long long 
using namespace std;
ll exgcd(ll a,ll b,ll &x,ll &y){
	if(!b){
		x=1;y=0;
		return a;
	}
	else{
		ll tx,ty;
		ll d=exgcd(b,a%b,tx,ty);
		x=ty;y=tx-(a/b)*ty;
		return d;
	}
}
int main(){
	ll a,b,k,x,y;scanf("%lld%lld%lld",&a,&b,&k);
	ll d=exgcd(a,b,x,y);
	if(k%d){puts("no solution!");return 0;}
	else{
		x=x*k/d;
		y=(k-a*x)/b;
	}
	printf("%lld %lld\n",x,y);
	return 0;
}

欧拉定理

证明：

设 \(x_1,x_2,\dots,x_{\varphi(m)}\) 是 \([1,m]\) 里面与 \(m\) 互质的数，由于在 \(\bmod m\) 意义下两两不同且余数都与 \(m\) 互质

因此我们推理：\(ax_i\) 必定也是 \(\bmod m\) 意义下两两不同且余数都与 \(m\) 互质的数

所以：

拓展欧拉定理

推理：[Oi Wiki](欧拉定理 & 费马小定理 - OI Wiki)

乘法逆元

定义：若 \(ax\equiv 1\pmod b\) 且 \(a\) 与 \(b\) 互质，那么我们就能定义 \(x\) 为 \(a\) 的逆元，记为 \(a^{-1}\) ，所以我们也能称 \(x\) 为 \(a\) 在 \(\pmod b\) 意义下的倒数，此时我们对于 \(\dfrac{a}{b}~\pmod p\)，我们就可以求出 \(b\) 在 \(\pmod p\) 意义下的逆元，来代替 \(\dfrac{1}{b}\)

快速幂

由费马小定理：若 \(p\) 为素数，\(a\) 为正整数，且 \(a\) 、\(p\) 互质。则有 \(a^{p-1}\equiv 1\pmod p\)

所以

所以我们用快速幂算出来 \(a\times b^{p-2}\) 就有 \(\dfrac{a}{b}\) 的逆元的值了

#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
int mod;
ll power(ll k,ll p){
	ll ans=1;
	while(p){
		if(p&1) ans=ans*k%mod;
		k=k*k%mod;
		p>>=1;
	}
	return ans;
}
ll a,b;
int main(){
	scanf("%lld%lld",&a,&mod);//算a的逆元
	printf("%lld",a*power(b,mod-2)%mod);
	return 0;
}

拓展欧几里得

求解 \(ax\equiv c \pmod b\) 中 \(c=1\) 的情况。我们可以转化为求解 \(ax+by=1\) 的解

所以：

ll exgcd(ll a,ll b,ll &x,ll &y){
	if(!b){
		x=1;y=0;
		return a;
	}
	else{
		ll tx,ty;
		ll d=exgcd(b,a%b,tx,ty);
		x=ty;y=tx-(a/b)*ty;
		return d;
	}
}
int a,p,x,y;
int main(){
    scanf("%d%d",&a,&p);
    int d=exgcd(a,p,x,y);
    x=(x%p+p)%p;
}

线性求逆元

首先，我们设 \(p=kx+r\)

那么我们很容易发现：\(kx+r\equiv 0\pmod p\)

此时，我们左右同时乘上 \(k^{-1}r^{-1}\) 可得

\(kr^{-1}+x^{-1}\equiv 0\pmod p\)

\(\therefore x^{-1}\equiv -kr^{-1}\pmod p\)

把 \(k=\left\lfloor \dfrac{p}{x} \right\rfloor\) \(r=p \bmod x\) 代入，得

\(x^{-1}\equiv -\left\lfloor \dfrac{p}{x} \right\rfloor \times (p \bmod i)^{-1} \pmod p\)

阶乘求逆元

首先，有如下的一个关系：

\(inv_{i+1}=\dfrac{1}{(i+1)!}\)

\(inv_{i+1}*(i+1)=\dfrac{1}{i!}\times \dfrac{1}{n+1}\times (n+1)=\dfrac{1}{i!}=inv_i^{-1}\)

所以我们可以先求出 \(n\) 的逆元，然后逆推即可

同时，我们也可以发现 \(\dfrac{1}{i}\) 的逆元就是：\(\dfrac{1}{i!}\times (i-1)!=\dfrac{1}{n}\pmod p\)

Lucas

定理：

中国剩余定理(CRT)

定理：对于下列一些式子的整数求出符合条件的最小的正整数 \(x\)

首先，若\((m_1,m_2\dots m_n)\)两两互质

我们即可直接令 \(M=m_1\times m_2\dots\times m_n\)

则令 \(M_i=\dfrac{M}{m_i}\)

当 \(x\) 满足 $x = x_1\times M_1\times M_1^{-1}+x_2\times M_2\times M_2^{-1}\dots $ 时

一定符合上面的式子

莫比乌斯反演

形式一：

证明：

我们容易发现：对于右边的式子 \(\sum_{i\mid x}g(i) \sum_{d\mid \frac x i} \mu(d)\)

结合莫比乌斯函数刚才推的性质2，我们很容易得到该式 \(=f(x)\)

得证

形式二：