数学是科学的女皇，数论是数学的女皇。 ——高斯
\[\Huge{\Large{}}\mathcal{Q\!\!\!X} \]\(\text{Gcd} \& \text{Lcm}\)
最大公因数和最小公倍数，基本上都是一些杂题。这里有一个性质：
\[\text{lcm}(a,b) = \frac{ab}{\gcd{(a,b)}} \]这个东西是可以证明的。
设有可重集合 \(A,B\) 满足
\[a=\prod A_i,b=\prod B_i \]而
\[\gcd(a,b) = \prod A\cap B,\text{lcm}(a,b) =\prod A\cup B ,ab=\prod (A+B) \Large{\circ} \small \! \! \! \! 1 \]根据集合论，
\[A\cup B=(A+B) - A\cap B \]则
\[\prod A\cup B = \frac{\prod A+B}{\prod A\cap B} \]将 \(\Large{\circ} \small \! \! \! \! 1\) 式代入上式，可以得到
\[\text{lcm}(a,b) = \frac{ab}{\gcd{(a,b)}} \]证明完毕。
还有一个 \(\text{lcm} (a,b)\) 是 \(a,b\) 的分解质因数结果的并集之积这个性质，因为这个太过简单所以在这里不证明了。
例题
- 根据这个性质有一道 \(\color{black}{P4626}\) 的题，可以用上面的定理进行推导，把每一个质数筛出来，然后找到一个最大的 \(k\) 满足 \(p_i ^{k_i} \leq n\) 将答案乘上一个 \(p_i ^{k_i}\) 就好了，可以证明只有 \(p_i ^{k_i}\) 这些以 \(p_i\) 为底的质数在 \([1,n] \cup \mathcal{Z}\) 这种的分解质因数结果。
\(Euler's\ Sotient\ Function\)
这个是欧拉筛法 \(/\) 欧拉函数。
首先给出欧拉函数的定义，也就是经典的 \(\varphi(n)=\sum _{i=1} ^n [gcd(i,n)=1]\)
人话就是在 \(n\) 以内与 \(n\) 互质的数的数量。
那么这个鬼畜玩意有什么性质呢？
下面用了《算法竞赛》上面的一堆东西。
-
欧拉函数是一个积性函数，当然并不是完全积性函数。也就是对于两个互质的两个数 \(p,q\) 存在 \(\varphi(p)\varphi(q)=\varphi(pq).\)
-
对于任意一个正整数 \(n\) 一定满足 \(n=\sum _{d|n} \varphi (d).\) 至于证明可以参考《算法竞赛》。
-
欧拉定理：\(a^{\varphi(m)} \equiv 1 \pmod m.\) 要求 \(a,m\) 互素。
-
一个鬼畜的常用性质：设 \(n\) 的质因数分解是 \(\prod p_i ^{k_i}\)
这个公式有两个特殊情况：当 \(n\in P\) 时 \(\varphi(n)=n-1.\) 当 \(n=p^k\) 时 \(\varphi(n)=p^{k-1}\varphi(p)\)
所以可以用试除去找到单个 \(\varphi(x).\) 复杂度仅有 \(\Theta (\sqrt x).\) 奇怪的 \(\sqrt x\) 算法又增加了。
欧拉筛可以用 \(O(n)\) 的复杂度求出 \([1,n]\cap Z\) 的欧拉函数值。
\[\mathcal{QXDATA} \]inline void Init(void){
phi[1]=1;
for(int i=2;i<=n;++i){
if(!vis[i]) prime[++cnt]=i,phi[i]=i-1,vis[i]=true;
for(int j=1;j<=cnt;++j){
if(i*prime[j]>n) break;
vis[i*prime[j]]=true;
if(!(i%prime[j])){
phi[i*prime[j]]=phi[i]*prime[j];
break;
}
phi[i*prime[j]]=phi[i]*phi[prime[j]];
}
}
}
- 例题 \(1\) 求
根据上面欧拉函数的性质 2. 可以将原式等量代换成
\[\sum _{i=1} ^n\sum _{j=1} ^n\sum _{d|gcd(i,j)} \varphi (d) \]然后如果 \(d|gcd(i,j)\) 就有 \([d|i][d|j].\) 将 \(d\) 的贡献提前，得原式可化为
\[\sum _{d=1} \varphi(d) \sum _{i=1} ^n \sum _{j=1} ^n [d|i][d|j] \]根据 \(\sum\) 的性质原式可化为
\[\sum _{d=1} \varphi(d) \sum _{i=1} ^n [d|i] \sum _{j=1} ^n [d|j] \]根据数论的性质原式可化为
\[\sum _{d=1} \varphi(d) \left[\frac{n}{d}\right] \]上面的中括号是高斯函数，也就是向下取整。
这个公式可以 \(Euler\) 求出 \(\varphi\) 然后秒杀。我都会写。
\(Chinese\ Remainer\ Thoerem\)
先提出一种很简单的问题：
\[\begin{cases} x \equiv 2\pmod 3\\ x \equiv 3\pmod 5\\ x \equiv 2\pmod 7\\ \end{cases}\]求解 \(x_{\min}\) 。这个问题在公元 \(3\) 世纪就提出了，答案显然是 \(23\)。
那么如果这个问题推广又应该怎么做啊？
\[\begin{cases} x \equiv a_1\pmod {m_1}\\ x \equiv a_2\pmod {m_2}\\ \qquad \ \ \ \ \vdots \\ x \equiv a_3\pmod {m_3}\\ \end{cases}\]其中 \(\{a_i\},\{m_i\}\) 是常数。求解最小的 \(x\)。
我们考虑扩展 \(crt\) (因为普通 \(crt\)) 我也不会证啊。。
\(Extend\ Chinese\ Remainer\ Thoerem\)
考虑对同余式子进行合并。
由 \(x \equiv a_1\pmod {m_1}\) 得，\(x=km_1+a_1.\)
代入 \(x \equiv a_2\pmod {m_2}\) ，得 \(km_1+a_1 \equiv a_2 \pmod{m_2}.\)
解方程得 \(k\equiv \frac{a_2-a_1}{m_1} \pmod{m_2}.\)
这个 \(k\) 可以通过逆元求解，则 \(x\equiv \frac{a_2-a_1}{m_1} \pmod{m_2}.\)
依次合并，然后注意一下 \(n=1\) 的情况， \(\mathcal{SOLVED.}\)
\(\mathcal{QX\ DATA}\)
LL CRT(void){
LL x,y;
LL m1=dt[1].m,a1=dt[1].a;
LL ans=0;
for(int i=2;i<=n;++i){
LL a2=dt[i].a,m2=dt[i].m;
LL a=m1,b=m2,c=(a2-a1%m2+m2)%m2;
LL d=exgcd(a,b,x,y);
if(c%d!=0) return -1;
x = x*c/d%(b/d);
ans = a1+x*m1;
m1=m2/d*m1;
ans=(ans%m1+m1)%m1;
a1=ans;
}
return ans;
}
\(Fermat's\ Little\ Theorem\)
费马小定理可以求解 \(\frac{b}{a} \bmod p.\) 要求 \(p\) 是质数。
公式如下 \(\frac{b}{a} \bmod p = b\times inv(a).\)
其中 \(inv(a)\equiv a^{-1} \equiv a^{p-2} \pmod p.\)
其中 \(a^{p-2}\) 可以快速幂。
例题 \(:\)
- \(\color{black}{}P5431\). 可以对 \(\{a\}\) 同分然后输出 \(ans\)，然后莫名其妙就 \(AC\) 了。其中计算 \(\frac{S}{a_i}\) 可以预处理前缀后缀积。
\(Mobius\ Function\)
了解到了一种奇怪的函数：莫比乌斯函数。
\[\mu(n) = \begin{cases} 1 &n=1\\ (-1)^r & n=\prod p (i\not =j,p_i \not = p_j) \\ 0 & Otherwise\end{cases} \]这个函数好像很奇怪，并且用处也好像没有，虽然一眼看去这个肯定是一个系数，但是用处就很古怪了。
先给出一些关于它的性质：
\[\sum _{d|n} =\begin{cases} 1 &n=1 \\ 0 & n>1\end{cases} \]证明省略。
那么这个看起来很鬼畜的东西有什么用呢？
有一个算术函数 \(f\) , 还有一个函数 \(F(n)=\sum _{d|n} f(d)\) ，那么 \(F\) 是和 \(f\) 有关的。显然我们可以通过带入消元法在了解 \(f\) 的情况下求出 \(F\) ，而且复杂度并不见得很高昂。
在列了一堆方程之后可以发现 \(f(i)\) 总是由 \(\sum _{d|n} \pm F(d)\) 得到。这样的话就要引出 \(F\) 前面的系数了。可以经过观察得到
\[f(n) = \sum _{d|n} \mu (d) F(\frac{n}{d}) \]嗯，这样就有价值了啊 ~
但是这样还是不够。
还需要知道一个东西 \([\gcd(a,b)=1] = \sum _{d|a,b} \mu(d)\)
原因是上面莫比乌斯函数的一个性质，也就是 \(\sum _{d|n}\) 的性质。由此可以得到 \(\sum _{d|n} \mu (d) = [n=1]\)
这样的话带入一下就好了。这样带有 \(\gcd\) 的方程就可以巧妙地用 \(\mu\) 来求解了。
- 例题 \(1\) 求解
人话就是 \(n,m\) 以下的有序可重复数对互质的方案总数。
这个式子可以根据上面的式子化为
\[\sum _{i=1} ^n \sum _{j=1} ^m \sum _{d|\gcd(i,j)} \mu (d) \]计算每一个 \(d\) 的贡献，把最后一个 \(\Sigma\) 放到前面，可化为
\[\sum _{d=1} ^{\max \{n,m\}} \mu (d) \sum _{i=1} ^n [i|n] \sum _{j=1} ^m [j|n] \]然后观察后面两个 \(\Sigma\) ，发现计算的是 \(i\) 的倍数在 \([1,n]\) 区域内出现的频数。原式可化为
\[\sum _{d=1} ^{\max\{n,m\}} \mu(d) \left[\frac{n}{d}\right] \left[\frac{m}{d}\right] \]这里可以暴力计算了。当然也可以数论分块优化，还要用前缀和优化优化。
- 例题 \(2\) 求解
暴力除法，原式 \(=\)
\[\sum _{i=1} ^{\left [ \frac{n}{k}\right]} \sum _{j=1} ^{\left [ \frac{m}{k}\right]} [\gcd(i,j)=1] \]这样就变成熟悉的认知了。
- 例题 \(3\) 求解
求
\[\sum _{i=1} ^n \sum _{j=1} ^m lcm(i,j) \]\(n,m \leq 10^7 ,\ T\leq 10^4\)
经过简单的莫比乌斯反演化简最后可以得到
\[\sum _{d=1} ^n d\sum_{k=1} ^{\left[\dfrac{n}{d}\right]} \mu(k)k^2 \sum_{i=1} ^{\left[\dfrac{n}{dk}\right]} i \sum_{j=1} ^{\left[\dfrac{m}{dk}\right]} j \]好了然后注意到后面的是等差序列，可以丢尽分块处理，所以考虑 设 \(T=dk, f(x)=\dfrac{x(x+1)}{2}\)
代入进去得到：
\[\sum _{d=1} ^n d\sum_{k=1} ^{\left[\dfrac{n}{d}\right]} \mu(k)k^2 f(\left[ \dfrac{n}{T}\right])f(\left[ \dfrac{m}{T}\right]) \]把后面两个 \(f\) 往前面扔。枚举 \(T.\) 就像之前 \(cbh\) 同学往前枚举 \(pd\) 是同样的道理。得到
\[\sum_{T=1}^{n} f(\left[ \dfrac{n}{T}\right])f(\left[ \dfrac{m}{T}\right]) \sum_{d|T} d\mu(d) T \]设 \(F(T) = \sum_{d|T} d\mu(d) T.\)
那么原式就可以直接暴力二维整除分块了。
至于 \(F\) 函数在 \(\texttt{Euler}\) 筛法中处理。
\(BSGS\)
一种求解奇怪的同余方程的算法。先给一个题面。
给定常数 \(b,n,p\) ，求 \(b^l \equiv n \pmod p\) 的 \(l\) 的最小整数解。
首先设 \(t=sqrt(p)+1.\) 然后再设一个 \(l=kt-m\)，那么原式可化为
\[b^{kt-m}\equiv n \pmod p \]根据幂的基本性质原式可化为
\[\frac{b^{kt} }{b^m} \equiv n \pmod p \]去分母，得
\[b^{kt} \equiv b^m \times n \pmod p \]前面的 \(kt-m\) 的 \(-m\) 项也可以写作 \(+m\) 但是会求一个逆元，消耗了 \(O(\log_2 n)\) 的复杂度，显然是不可取的。所以这里用到了一个人为的优化。
这里考虑维护一个 \(Hash\) 池标记满足 \(b^m \times n \equiv x\) 的 \(m\) ，方便后期处理。
然后由于 \(t\) 是常数，可以枚举 \(k\in [0,t] \cap Z\)，然后当 \(b^{kt}\) 在哈希池子里面有值的时候就扯出来处理处理就完事了。
这个东西好像还是很不好调试的。中文名：大步小步算法。
inline ll BSGS(void){
n%=p,t=ceil(sqrt(p));
ll res=1;
for(int i=0;i<=t;++i)
lake[n*res%p]=i,(res*=b)%=p;
for(int k=0;k<=t;++k){
ll value=qpow(b,k*t),M=lake[value];
if(M&&k*t-M>0)
return k*t-M;
}
return -1ll;
}
其中 qpow 的部分还是可以优化的。下面是优化的版本：
lake.clear();
t=ceil(sqrt(p));
ll res=1;
for(int i=0;i<=t;++i)
lake[res*b%p]=i,(res*=a)%=p;
ll bs=Qpow(a,t);
res=1;
for(int k=0;k<=t;++k){
ll m=lake[res%p];
if(m&&t*k>=m) return t*k-m;
(res*=bs)%=p;
}
这样做还可以省去一只 \(\log\)。
例题：
1. \(\color{black}{}P4884\)。这道题可以考虑将 \(111...1(n\rightarrow 1)\) 化为 \(\frac{10^n-1}{9}\) 然后原式可化为
\[\frac{10^n-1}{9}\equiv K \pmod p \]去分母，得
\[{10^n-1}\equiv 9K\pmod p \]移项得
\[10^n\equiv 9K+1 \pmod p \]然后就可以快乐的套模板了。所以多这一个憨憨公式就可以评紫对吗
标签：right,frac,数论,sum,pmod,equiv,left From： https://www.cnblogs.com/chihirofujisaki/p/18218346/TheQueenOfMath