zcmimi's blog

arrow_backgcd共4篇文章

avatar
zc
2020-10-14 18:06:50

查看原题

点击跳转

结论: \gcd(f_n,f_m)=f_{\gcd(n,m)},然后矩阵快速幂加速即可

证明:

m>n

引理:

  • \gcd(f_n,f_{n+1})=1

    根据辗转相减法, \gcd(f_n,f_{n+1})=\gcd(f_n,f_{n+1}-f_n)=\gcd(f_n,f_{n-1})

    所以 \gcd(f_n,f_{n+1})=\gcd(f_n,f_{n-1})=\dots=\gcd(f_2,f_1)=1

  • f_{n+m}=f_nf_{m-1}+f_{n+1}f_m

    数学归纳法:

    1. n=m=1时,成立
    2. 假设m,n\le k时成立,当n=k+1时:

      \begin{aligned} f_{n+m} &=f_{m+(k+1)}=f_{k+(m+1)}\\ &=f_mf_{k-1}+f_{m+1}f_k\\ &=f_mf_{k-2}+f_{m+1}f_k + f_{m+1}f_{k-1}+f_{m+2}f_k\\ &=f_{m+1}(f_{k}+f_{k-1})+f_{m}(f_{k-1}+f_{k-2})\\ &=f_kf_m+f_{k+1}f_{m+1} \end{aligned}

  • \gcd(f_{n+m},f_n)=\gcd(f_n,f_m)

    \begin{aligned} \gcd(f_{n+m},f_n) &=\gcd(f_nf_{m-1}+f_{n+1}f_m,f_n)\\ &=\gcd(f_{n+1}f_m,f_n)\\ &=\gcd(f_{n+1},f_n)\cdot\gcd(f_m,f_n)\\ &=\gcd(f_m,f_n) \end{aligned}

\begin{aligned} \gcd(f_n,f_m) &=\gcd(f_n,f_{m-n+n})\\ &=\gcd(f_n,f_{m-n}f_{n-1}+f_{m-n+1}f_n)\\ &=\gcd(f_n,f_{m-n}f_{n-1}) \end{aligned} \\ \because \gcd(f_{n},f_{n+1})=1\\ \therefore \gcd(f_n,f_{m-n}f_{n-1})=\gcd(f_n,f_{m-n})

这样一直碾转相减下去,就是f_{\gcd(n,m)}

avatar
zc
2020-09-14 16:15:00
查看原题

点击跳转

从大到小枚举n的因子x

如果能够满足那么x+2x+\dots+kx\le n

x(1+2+\dots+k)\le n\\ \dfrac{xk(1+k)}{2}\le n\\ xk(1+k)\le 2n

其中x\le \dfrac{2n}{k(1+k)}

找到最大的x后,按顺序输出x,2x,\dots+(k-1)x,最后一个数为n减去前面的数的和

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

  1. 如果个数中没有奇数,那么答案就是所有数字的gcd,然后构造答案就是输出\frac {gcd}2个回文串

  2. 如果个数中只有一个奇数,那么答案也是所有数字的gcd,然后构造答案就是输出gcd个回文串,个数为奇数的颜色放在回文串的中间

  3. 如果个数中有两个或以上的奇数,那么答案就是0,因为两个奇数就已经构造不出有优美cut的环来了

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

一段区间检查后能不被吃掉的汉堡满足其他汉堡的能量值都是它的倍数

那我们就求出区间\gcd. 而这个汉堡的能量值必须等于区间gcd,所以它的能量值也是区间最小值。

那我们就再记录区间最小值并且记录数量

那么满足这个复杂度而且最方便的当然是线段树了

1/1
Search
search