本文内容：同余，剩余类，完全剩余系，同余最短路，乘法逆元，笛卡尔积，既约剩余系，完全余数集合，欧拉函数及其性质，Lucas 定理。

本文及以后所设的字母，若无特殊约定，均为整数或正整数。

同余

若两个整数 $a$ 和 $b$ 满足 $a-b$ 能够被正整数 $m$ 整除，即 $m\mid a-b$ ，那么就称整数 $a$ 与 $b$ 对模 $m$ 同余，记作

a \equiv b \pmod m

$\LaTeX$ ：a \equiv b \pmod m。

如果它们都是正数，那么上面的式子等价于 $a$ 与 $b$ 分别用 $m$ 去除，余数相同。

举例：

7^7 \equiv 2023 \pmod{7!}

剩余类

对于一个整数 $m$ ，可以把所有整数分成 $m$ 类，每类中的元素对于 $m$ 都同余。每一类都叫做 $m$ 的一个剩余类。

比如 $5$ ，有 $5$ 个剩余类，对 $0$ 同余的有 $\{-5,0,5,\dots\}$ 。

$\LaTeX$ ：\{-5,0,5,\dots\}。

完全剩余系

从 $m$ 的每个剩余类中任抽出一个数组成的集合，称为 $m$ 的完全剩余系。

比如 $5$ ，它的一个完全剩余系是： $\{0,1,2,3,4\}$ 。

同余最短路

问题：给定 $n$ ， $a_{1\dots n}$ ， $l$ ， $r$ ，求出有多少 $b\in[l,r]$ 可以使等式

\sum_{i=1}^n a_ix_i=b

存在非负整数解。

$\LaTeX$ ：a_{1\dots n} b\in[l,r] \sum_{i=1}^n a_ix_i=b。

解：考虑如何不重不漏地统计所有可能的 $b$ 。

取任意一个 $a$ ，若某个 $b$ 合法，则 $b$ 一定可表示为 $m+ka$ （ $m=b \bmod a$ ）。

得到一个合法的 $b$ 后，在数轴上每次后移周期 $a$ ，都是合法的。

故通过 $a$ ，利用 $a$ 的完全剩余系 $A=\{0,1,2,\dots,a-1\}$ 对 $b$ 进行分类，分为 $a$ 类。

令 $b_i\in A$ ，我们关心的是从 $0$ 开始，第一个与 $b_i$ 对模 $a$ 同余的位置，即由 $0$ 号节点出发到 $dis \bmod a$ 号节点的最短路。求得这个，即可直接计算出答案。

#include<bits/stdc++.h>
using namespace std;

namespace _yz
{
	typedef long long ll;
	const ll N=1000000+10;
	const ll inf=2147483647999999999;
	queue<ll>q;
	ll n,l,r,a[20],dis[N],vis[N],ans=0;
	void spfa()
	{
		q.push(0);
		dis[0]=0;
		vis[0]=1;
		while(!q.empty())
		{
			ll now=q.front();
			q.pop();
			vis[now]=0;
			for(ll i=1;i<=n;i++)
			{
				ll to=(dis[now]+a[i])%a[1];
				if(dis[to]>dis[now]+a[i])
				{
					dis[to]=dis[now]+a[i];
					if(!vis[to])
					{
						q.push(to);
						vis[to]=1;
					}
				}
			}
		}
	}
	ll query(ll x)
	{
		ll ret=0;
		for(ll i=0;i<=a[1]-1;i++)
			if(dis[i]<=x)
				ret+=(x-dis[i])/a[1]+1;
		return ret;
	}
	void main()
	{
		scanf("%lld%lld%lld",&n,&l,&r);
		for(ll i=1;i<=n;i++) scanf("%lld",a+i);
		for(ll i=0;i<=a[1]-1;i++) dis[i]=inf;
		spfa();
		printf("%lld\n",query(r)-query(l-1));
		return;
	}
}
int main()
{
	_yz::main();
	return 0;
}

乘法逆元

若 $a$ ， $x$ ， $m$ 满足：

ax\equiv1\pmod m

则 $x$ 是 $a$ 的模 $m$ 乘法逆元（又称为数论倒数），记为 $a^{-1}\pmod m$ ，且 $a$ 是 $x$ 的模 $m$ 乘法逆元，记为 $x^{-1}\pmod m$ ，即乘法逆元是相互的。

显然当且仅当 $(a,m)=1$ 时， $x$ 存在逆元。

显然若 $(a,m)=1$ ，则 $(a^{-1},m)=1$ （乘法逆元是相互的）。

$\LaTeX$ ：a^{-1}\pmod m。

求法

$m$ 为素数，且 $a \not\mid m$ ，费马小定理可求。
仅满足 $(a,m)=1$ ，exgcd 求解同余方程。
求小于素数 $p$ 的所有数的模 $p$ 的乘法逆元，线性递推求。
$i^{-1}\equiv-r^{-1}q\equiv-(p \bmod i)^{-1}\lfloor\dfrac{p}{i}\rfloor\pmod p$

笛卡尔积

两个集合 $X$ 和 $Y$ 的笛卡尔积，又称直积，表示为 $X\times Y$ 。

则 $X\times Y=\{(x,y)\mid x\in X,y\in Y\}$ 。其中 $(x,y)$ 为有序对。

如， $\{1,2\}\times\{a,b\}=\{(1,a),(1,b),(2,a),(2,b)\}$ 。

既约剩余系

若 $A$ 是 $a$ 的完全剩余系，则集合 $B=\{b\in A\mid (a,b)=1\}$ 是 $a$ 的既约剩余系。

完全余数集合

若 $A$ 是 $a$ 的既约剩余系，且 $\forall x\in A$ ，有 $x<a$ ，则 $A$ 是 $a$ 的完全余数集合。

显然， $|A|=\varphi(a)$ 。

欧拉函数及其性质

$\varphi(n)$ ：对于一个正整数 $n$ ，小于 $n$ 且和 $n$ 互质的正整数的个数。是积性函数。

积性证明

设 $\gcd(a,b)=1$ （简写为 $(a,b)=1$ ）； $a$ ， $b$ ， $ab$ 的完全余数集合是 $A$ ， $B$ ， $C$ 。

显然，存在映射 $f:C\rightarrow A\times B$ ，设 $z\in C$ ，则其映射 $(z\bmod a,z\bmod b)\in A\times B$ 。

为了对像我一样的蒟蒻友好一点，给一点提示。结合下式即可易得：
$(a,m)=(b,m)=1 \iff (ab,m)=1$ 。
$(a,b)=(b,a\bmod b)$
注：若从集合的观点看这些数，把这些数看作一些质因子的集合，那么上面那些式子也是显然的。

显然，存在逆映射 $f^{-1}:A\times B\rightarrow C$ 。

提示：中国剩余定理（CRT）对于解的存在性判断和解的分布。

所以， $A\times B$ 与 $C$ 间存在双射， $|A\times B|=|C|$ 。

易知， $|A\times B|=|A|\times|B|=\varphi(a)\varphi(b)$ ，且 $|C|=\varphi(ab)$ 。

于是，我们得到 $\varphi(ab)=\varphi(a)\varphi(b)$ 。

一些式子

\varphi(x)=x\prod_{i=1}^n(1-\dfrac{1}{p_i})

本式为欧拉函数公式。
其中， $p_i$ 是 $x$ 的质因子， $n$ 为 $x$ 质因子个数。
特殊地， $\varphi(1)=1$ 。
公式可由积性函数性质或者容斥原理求得。

\varphi(p)=p-1

其中 $p$ 为质数。显然。

\varphi(2n)=\varphi(n)

其中 $n$ 为奇数。显然。

\varphi(n)=p^k-p^{k-1}=(p-1)p^{k-1}

其中 $p$ 为质数， $n=p^k$ 。
显然。可认为是数轴上每隔上 $p$ 个数就挖去一个数，剩下的都互质。

\varphi(ab)=a\varphi(b)

其中若 $a$ ， $b$ 的质因子集合为 $A$ 和 $B$ ，则满足 $A\subseteq B$ 。
结合欧拉函数公式易得。

S=n\varphi(n)/2

其中 $S$ 为所有小于 $n$ ，且与 $n$ 互质的数的和。
根据若 $(n,i)=1$ ，则 $(n,n-i)=1$ 这一结论易得。

\sum_{d|n}\varphi(d)=n

~~证明待填坑。~~

Lucas 定理

设 $p$ 为素数， $a,b\in N^*$ ，并且

a=a_kp^k+a_{k-1}p^k-1+\dots+a_1p+a_0,

b=b_kp^k+b_{k-1}p^k-1+\dots+b_1p+b_0,

这里 $0\le a_i,b_i\le p-1$ ，且都为整数（把 $a$ ， $b$ 表示为 $p$ 进制数）， $i=0,1,2,\dots,k$ 。则有：

C_a^b\equiv C_{a_k}^{b_k}\cdot C_{a_{k-1}}^{b_{k-1}}\dots C_{a_0}^{b_0}\pmod p

引理： $\forall j\in[1,p-1]，C_p^j=\dfrac{p}{j}C_{p-1}^{j-1}\equiv0\pmod p$ 。

变式：

\large C_m^n\equiv C_{\lfloor\frac{m}{p}\rfloor}^{\lfloor\frac{n}{p}\rfloor}\times C_{m \text{ mod } p}^{n \text{ mod } p}\pmod p

代码：

#include<bits/stdc++.h>
using namespace std;
namespace _yz
{
	typedef long long ll;
	const ll N=200000+10;
	ll n,m,p,mul[N],inv[N];
	void init()
	{
		mul[0]=mul[1]=1;
		for(ll i=2;i<=n+m;i++)
			mul[i]=mul[i-1]*i%p;
		inv[1]=1;
		for(ll i=2;i<=p-1;i++)
			inv[i]=((-p/i*inv[p%i])%p+p)%p;
		return;
	}
	ll C(ll n,ll m)
	{
		if(n<m) return 0;
		return mul[n]*inv[mul[m]*mul[n-m]%p]%p;
	}
	ll Lucas(ll n,ll m,ll p)
	{
		if(m==0) return 1;
		return C(n%p,m%p)*Lucas(n/p,m/p,p)%p; 
	}
	void main()
	{
		ll T;
		scanf("%lld",&T);
		while(T--)
		{
			scanf("%lld%lld%lld",&n,&m,&p);
			init();
			printf("%lld\n",Lucas(n+m,n,p));
		}
		return;
	}
}
int main()
{
	_yz::main();
	return 0;
}