UOJ Logo qx的博客

博客

三角形

2024-05-12 13:23:54 By qx

数据结构

2023-11-30 18:15:16 By qx

$$ \mathcal{ST}$$

像某个 $Cbh$ 一样 $st$ 表都不会写还是不好的。所以写一篇 $st$ 表。

$ST$ 表支持维护区间问题,并且要求静态。可以达到预处理 $O(n\log n)$,而单词查询 $O(1)$ 的恐怖效率。空间复杂度 $O(n\log n)$ ,想比于线段树其应用范围稍显狭窄。

$\mathcal{But...}$ $\mathcal{ST}$ 的单词查询是 $O(1)$ 的。

下面主要以 $\min$ 操作为例介绍

$\mathcal{ST}$ 的思想主要基于倍增。

先要 $Init(log2)$ 当然如果你不嫌弃 $C++$ 的大常数 $\log_2$ 的话也不是不行。

只需要 $Init([1-n])$ 的 $\log_2$ 就好了。这一步主要是为了应付后面倍增要求。显然,$\log_2(x)=log_2(\left[\frac{x}{2}\right])+1$ 理由不想多说。按照这个步骤初始化即可。

$$\mathcal{STEP . 1}$$

然后就是预处理。可以得到一个 $\min$ 特有的关系式,大概就是这个相貌:

$$\min_{i=l} ^r a[i] = \min\{\min _{i=l} ^{k\leq r} a[i],\min_{k\geq l} ^r a[i]\}$$

等式右边的两项可以通过刚刚的方法求得。

这样就可以开始推导推导了:设 $dp[i][j]$ 表示 $\min _{k=l} ^{l+2^j} a[k]$,这里就可以出来一个转移方程:

$$dp[i][j]=\min\{dp[i][j-1],dp[i+2^{j-1}][j-1]\}$$

理由如上。

$$\mathcal{STEP.2}$$

查询操作。

$$\min_{i=l} ^r a[i] = \min\{dp[l][k],dp[r-2^k][k]\}$$

其中 $k=\log_2(r-l+1)$

理由还是如上。

$$\mathcal{STEP.3}$$

吸取了某个叫 $\mathcal{CBH}$ 同学的教训,我们可以知道 $k$ 就是 $k$ ,不要 $k-1.$

上代码。

// here is Init
void init(){
    lg[0]=-1;
    FOR(i,1,n) lg[i]=lg[i>>1]+1;
    FOR(i,1,n) dp[i][0]=a[i];
    int lim=lg[n];
    FOR(k,1,lim)
        FOR(s,1,n+1-(1<<k))
            dp[s][k]=max(dp[s][k-1],dp[s+(1<<(k-1))][k-1]);
}
// here is Query
l=read();r=read();
int k=lg[r-l+1];
cout<<max(dp[l][k],dp[r-(1<<k)+1][k])<<'\n';

那么除了 $\min$ 之外 $\mathcal{ST}$ 还可以维护 $\mathcal{GCD,MAX,OR,LCM}$ 之类的东西。

$$\mathcal{O(n\log n)+O(n \log n)+O(1)}$$

数论

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

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

qx Avatar