对于一些小的数学的方法的一些记录

这里只是一些做题时用到的数学小技巧

• 转【hdxrie的数学积累】

---

• 求$x^m\equiv x(mod\ p)p\in\mathbb{P}$xm≡x(mod p)p∈P，且$x\in[0,p-1]$x∈[0,p−1]的满足条件的$x$x的个数。

答案为$gcd(m-1,p-1)+1$gcd(m−1,p−1)+1个。

证明：

首先对于$0$0所有情况都满足，所以先加个$1$1。

然后对于$x\not=0$x̸​=0，而且$p$p为质数，所以$x$x肯定有逆元，所以我们将原式变形得到$x^{m-1}\equiv1(mod\ p)$xm−1≡1(mod p)

然后因为$p$p为质数，那么可求一个它的原根，记为$g$g，我们根据原根的定义可知，当$g^k\equiv w(mod\ p),k\in[1,p-1]$gk≡w(mod p),k∈[1,p−1]，只有$k=p-1$k=p−1时$w=1$w=1，对于其他任何的$k$k，$w$w都不一样，所以我们可以将原式中的$x$x，转换为$g^y$gy，也就是$x\equiv g^y(mod\ p)$x≡gy(mod p)。

所以原式就变成了$(g^y)^{m-1}\equiv 1(mod\ p)$(gy)m−1≡1(mod p)，我们用欧拉定理对指数进行处理。

欧拉定理：$x^y\equiv x^{y\ mod\ \varphi(p)}(mod\ p)$xy≡xy mod φ(p)(mod p)

所以将指数提出，原式变成$y(m-1)\equiv 0(mod\ (p-1))$y(m−1)≡0(mod (p−1))，然后由于$m,p-1$m,p−1不一定互质，所以我们令$k=gcd(p-1,m-1)$k=gcd(p−1,m−1)，原式可以变成$y\frac{m-1}{k}\equiv 0(mod\ \frac{p-1}{k})$ykm−1​≡0(mod kp−1​)，由于$gcd(\frac{m-1}{k},\frac{p-1}{k})=1$gcd(km−1​,kp−1​)=1，所以这两个互质，那么同余为$0$0只有$y$y为$\frac{p-1}{k}$kp−1​的倍数，那么由于$y\in[1,p-1]$y∈[1,p−1]那么$y$y只有$k$k种选法，根据原根的定义，那么同理$x$x也有$k$k种，所以算上$x=0$x=0答案就为$gcd(p-1,m-1)+1$gcd(p−1,m−1)+1。

---

• $x^m\equiv x(mod\ n)\Leftrightarrow x^m\equiv x(mod\ p_i)$xm≡x(mod n)⇔xm≡x(mod pi​)，其中$n=\prod p_i$n=∏pi​，且$p_i$pi​为质数并都不相同。

证明：

这个相当于逆中国剩余定理，对于原式，我们可以写成$x^m-k_1n=x-k_2n$xm−k1​n=x−k2​n，那么将$n$n展开可得$x^m-k_1(\prod p_i)=x-k_2(\prod p_i)$xm−k1​(∏pi​)=x−k2​(∏pi​)

然后我们对于每一个$p_j$pj​，可以写出一个式子：
$x^m-k_1(\prod p_i)\equiv x-k_2(\prod p_i)(mod\ p_j)$xm−k1​(∏pi​)≡x−k2​(∏pi​)(mod pj​)
也就等价于$x^m\equiv x(mod\ p_j)$xm≡x(mod pj​)（因为减去的部分给模掉了）

加入有$c$c个$p_i$pi​，那么我们可以的到$c$c个同余式，将其分别解出，然后中国剩余定理合并一下，就可以得到原式的答案，所以当这些式子分别满足时，才能满足原式。

而当$x\in[1,n]$x∈[1,n]时，令最终答案为$ans$ans，假设这$c$c个同余式的每一个有$c_i$ci​个$x$x满足，由于在范围内最多只会有一个$x$x满足$ans$ans，所以在每个同余式中选出一个，那么最后就会有$\prod c_i$∏ci​个$x$x满足原式，所以$ans$ans的个数就为$\prod c_i$∏ci​。

---

• 对于$n$n个点的完全图的生成树有$n^{n-2}$nn−2个，有根生成树为$n^{n-1}$nn−1个。

证明：

用矩阵树或者prufer序列定理等证明就好啦我才不会告诉你我并不会证明╭(╯^╰)╮。

---

• 最大公约数的更相减损术

内容：$gcd(a,b)=gcd(a,b-a)(a\leq b)$gcd(a,b)=gcd(a,b−a)(a≤b)

可用于差分求区间$gcd$gcd询问修改。

其它应用：高精$gcd$gcd的简便写法

• $a$a偶数，$b$b奇数：$gcd(a,b)=gcd(\frac{a}{2},b)$gcd(a,b)=gcd(2a​,b)
• $a$a奇数，$b$b偶数：$gcd(a,b)=gcd(a,\frac{b}{2})$gcd(a,b)=gcd(a,2b​)
• $a$a奇数，$b$b奇数（$b\leq a$b≤a）：$gcd(a,b)=gcd(a-b,b)$gcd(a,b)=gcd(a−b,b)
• $a$a偶数，$b$b偶数：$gcd(a,b)=2\times gcd(\frac{a}{2},\frac{b}{2})$gcd(a,b)=2×gcd(2a​,2b​)

---

• 同余最短路

对于如下方程，求取$b\in[l,r]$b∈[l,r]中是的该方程有非负整数解的方案数。

$a_1x_1+a_2x_2+\cdots+a_nx_n=b$a1​x1​+a2​x2​+⋯+an​xn​=b

其中$a_i$ai​已知。

1. 首先我们选取$m=\min\limits_{i=1}^n\{a_i\}$m=i=1minn​{ai​}，令其为模数，因为对于小于$m$m的除了$x=0$x=0，其它任何方案是组合不出来的，因为至少方程值都为$m$m，那么$mod\ m$mod m余数就是在$0\sim m-1$0∼m−1内了。
2. 我们枚举$0\thicksim m-1$0∼m−1，将每个数字$(a_i+w)mod\ m$(ai​+w)mod m与枚举的数$w$w组合建边，边权为$a_i$ai​，表示当前数$w$w加上$a_i$ai​可以变成$(a_i+w)mod\ m$(ai​+w)mod m。
3. 我们跑单源最短路，从$0$0这个状态开始跑，求出每个状态点最小的能够满足它的值。
4. 对于每个状态点，也就是枚举$0\thicksim m-1$0∼m−1中的点，我们知道最小的满足值，那么就可以求出在$l\sim r$l∼r中有多少个在$mod\ m$mod m的意义下等于它，统计计入答案即可。

墨墨的等式[国家集训队]-luogu
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const int N=2e6+10;
int n;
ll Bs,Bt,inf,minv,A[N],up;
struct ss{
	int to,last;ll len;
	ss(){}
	ss(int a,int b,ll c):to(a),last(b),len(c){}
}g[N<<1];
int head[N],cnt;
void add(int a,int b,ll c){
	if(a==b) return;
	up=max(up,(ll)max(a,b));
	g[++cnt]=ss(b,head[a],c);head[a]=cnt;
}

struct node{
	ll val;int id;
	node(){}
	node(ll a,int b):val(a),id(b){}
	bool operator <(const node &a)const{return val>a.val;}
};

ll dis[N];
priority_queue <node> Q;

void dij(){
	memset(dis,0x3f,sizeof(dis));
	inf=dis[0];
	dis[0]=0;Q.push(node(0,0));
	while(!Q.empty()){
		node now=Q.top();Q.pop();
		int a=now.id,v;
		if(now.val>dis[a]) continue;
		for(int i=head[a];i;i=g[i].last){
			v=g[i].to;
			if(dis[v]>dis[a]+g[i].len){
				dis[v]=dis[a]+g[i].len;
				Q.push(node(dis[v],v));
			}
		}
	}
}
ll ans;
ll calc(ll v,ll low){
	return (Bt-v+minv)/minv-(low-1ll-v+minv)/minv;
}
int main(){
	scanf("%d%lld%lld",&n,&Bs,&Bt);
	minv=1e9;
	for(int i=1;i<=n;i++)scanf("%lld",&A[i]),minv=min(minv,A[i]);
	for(int i=1;i<=n;i++){
		for(int j=0;j<minv;j++){
			int p=(A[i]+j)%minv;
			add(j,p,A[i]);
		}
	}
	dij();
	for(int i=0;i<minv;i++){
		if(dis[i]==inf)continue;
		ll now=max(dis[i],Bs);
		if(now>Bt) continue;
		ans+=calc(i,now);
	}
	printf("%lld\n",ans);
	return 0;
}