UOJ Logo qx的博客

博客

数论

2023-11-26 13:54:38 By qx

数学是科学的女皇，数论是数学的女皇。 ——高斯

$$\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$ 的分解质因数结果的并集之积这个性质，因为这个太过简单所以在这里不证明了。

例题
  1. 根据这个性质有一道 $\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$ 互质的数的数量。

那么这个鬼畜玩意有什么性质呢？

下面用了《算法竞赛》上面的一堆东西。

  1. 欧拉函数是一个积性函数，当然并不是完全积性函数。也就是对于两个互质的两个数 $p,q$ 存在 $\varphi(p)\varphi(q)=\varphi(pq).$

  2. 对于任意一个正整数 $n$ 一定满足 $n=\sum _{d|n} \varphi (d).$ 至于证明可以参考《算法竞赛》。

  3. 欧拉定理：$a^{\varphi(m)} \equiv 1 \pmod m.$ 要求 $a,m$ 互素。

  4. 一个鬼畜的常用性质：设 $n$ 的质因数分解是 $\prod p_i ^{k_i}$

$$\varphi(n) =n\left(1-\frac{1}{p_1}\right)\left(1-\frac{1}{p_2}\right)...\left(1-\frac{1}{p_r}\right)=n\prod ^{r} _{i=1} \left( 1-\frac{1}{p_i}\right)$$

这个公式有两个特殊情况：当 $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. 例题 $1$ 求

    $$\sum_{i=1}^n \sum_{j=1}^n \gcd(i, j)$$

    根据上面欧拉函数的性质 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}$ 可以快速幂。

例题 $:$

  1. $\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. 例题 $1$ 求解

    $$\sum _{i=1} ^n \sum _{j=1} ^m [\gcd(i,j)=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. 例题 $2$ 求解

$$\sum _{i=1} ^n \sum _{j=1} ^m [\gcd(i,j)=k]$$

暴力除法，原式 $=$

$$\sum _{i=1} ^{\left [ \frac{n}{k}\right]} \sum _{j=1} ^{\left [ \frac{m}{k}\right]} [\gcd(i,j)=1]$$

这样就变成熟悉的认知了。

  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$$

然后就可以快乐的套模板了。所以多这一个憨憨公式就可以评紫对吗

评论

ghh2012
小学生：看不懂

发表评论

可以用@mike来提到mike这个用户，mike会被高亮显示。如果你真的想打“@”这个字符，请用“@@”。

Server time: 2024-11-21 14:23:39