阅读视图

2025-2026 赛季游记 && 退役记

2025年9月20日 20:27

<div class="note note-info"> <a href="https://blog.makerlife.top/post/S25-record-private">私密版</a> </div><h2 id="Day-70-CSP-S-初赛">Day -70 CSP-S 初赛</h2>2025/9/20进场的时候在门口堵了 20 分钟。今年好像比较简单，但怎么 ccf 码风这么好看了。<h2 id="Day-33">Day -33</h2>2025/10/27怎么已经有三个人停课了，这么急。不知道为什么今天状态很差，whk 也不想学，oi 也不敢停课。<h2 id="Day-30">Day -30</h2>2025/10/30找班主任请假在机房待了一上午，对着 noi 大纲复健板子。顺便把没打完的游戏打了。先天 ub 圣体，前有关同步后混用 <code>read()</code> 和 <code>cin</code>，后有动态开点线段树用 <code>std::vector</code> 的 <code>emplace_back()</code> 之后迭代器失效。很害怕考场写 ub。我怎么下午还要去体测？怎么体测的地方跳远垫子这么滑？诶我怎么腿直接亲地上了？rp--然后成功一瘸一拐的去了日照。<h2 id="Day-29">Day -29</h2>2025/10/31去日照的高速好像已经走了五六年了，甚至那几个隧道和大桥名字都快背过了。去试机，刚进机房就发现有个电脑蓝屏了，还在想谁这么倒霉。结果过去一看是我电脑。然后就被安排到了对面备用机器。<img src="https://img.makerlife.top/data/202511021931246.jpeg" alt="蓝屏的电脑">本机 1s <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>4</mn><mo>×</mo><msup><mn>10</mn><mn>8</mn></msup></mrow><annotation encoding="application/x-tex">4\times 10^8</annotation></semantics></math>4×108 次取模，还没有虚拟机，那我 ub 怎么办。<h2 id="Day-28-CSP-S-复赛">Day -28 CSP-S 复赛</h2>2025/11/01CSP 比赛日。做梦好像梦到四个文件全没加文件读写，吓醒了。7 点多直接去吃早饭，然后对着电脑看到 11 点。解压密码好像是人杰地灵，膜 <code>Ren5Jie4Di4Ling5%</code>。开 T1，一看诶这不是个 dp 吗？开写！诶？我 dp 怎么是 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi mathvariant="normal">Θ</mi><mo stretchy="false">(</mo><msup><mi>n</mi><mn>3</mn></msup><mi>log</mi><mo>⁡</mo><mi>n</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">\Theta(n^3\log{n})</annotation></semantics></math>Θ(n3logn) 的。哦是不是可以优化。并不是。哦观察样例发现好像最多的一列一定选 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mstyle displaystyle="true" scriptlevel="0"><mfrac><mi>n</mi><mn>2</mn></mfrac></mstyle></mrow><annotation encoding="application/x-tex">\dfrac{n}{2}</annotation></semantics></math>2n？这玩意显然不对啊。哦还真不对。算了去看 T2。上了个厕所然后一眼会了 40pts 暴力加边然后 kruskal，飞速打完。坏了 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>c</mi><mo mathvariant="normal">≠</mo><mn>0</mn></mrow><annotation encoding="application/x-tex">c\neq 0</annotation></semantics></math>c=0 咋做，不懂。直到考完也没想到那玩意是用来 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi mathvariant="normal">Θ</mi><mo stretchy="false">(</mo><msup><mn>2</mn><mi>k</mi></msup><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">\Theta(2^k)</annotation></semantics></math>Θ(2k) 的。考完发现当时被降智了，本来对于一个被选的乡村 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>c</mi></mrow><annotation encoding="application/x-tex">c</annotation></semantics></math>c，直接加 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>n</mi></mrow><annotation encoding="application/x-tex">n</annotation></semantics></math>n 条边 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>c</mi><mo>↔</mo><mi>e</mi><mo separator="true">,</mo><mi>e</mi><mo>∈</mo><mo stretchy="false">{</mo><mn>1</mn><mo separator="true">,</mo><mo>…</mo><mo separator="true">,</mo><mi>n</mi><mo stretchy="false">}</mo></mrow><annotation encoding="application/x-tex">c\leftrightarrow e, e\in\{1,\dots, n\}</annotation></semantics></math>c↔e,e∈{1,…,n} 即可。但是为啥我考场对节点两两连边，加了 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mstyle displaystyle="true" scriptlevel="0"><mfrac><mrow><mi>n</mi><mo stretchy="false">(</mo><mi>n</mi><mo>+</mo><mn>1</mn><mo stretchy="false">)</mo></mrow><mn>2</mn></mfrac></mstyle></mrow><annotation encoding="application/x-tex">\dfrac{n(n+1)}{2}</annotation></semantics></math>2n(n+1) 条边啊？？？？？读了一遍 T3 发现没看懂，语言学还是太厉害了！直接去 T4，写了个 8 分跑路。哦 T3 是不是就是 AC 自动机上随便搞点东西，但我已经不会 acam 了，有空现推，先把暴力哈希写了。坏了哈希写了 3k 还没过，红温。好像已经 <code>5:30</code> 多了，我要去推 T1。又去读了一遍题，突然发现是不是直接选每个最大的，如果最终有一列超过 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mstyle displaystyle="true" scriptlevel="0"><mfrac><mi>n</mi><mn>2</mn></mfrac></mstyle></mrow><annotation encoding="application/x-tex">\dfrac{n}{2}</annotation></semantics></math>2n 就去调整对答案贡献少的人的选择，也许是对的？此时 <code>5:50</code> 多，感觉要写至少 3k 啊，不敢写了，写了如下注释遂跑路：<figure class="highlight cpp"><table><tr><td class="gutter"><pre>1 2 </pre></td><td class="code"><pre><code class="hljs cpp">// maybe greedy is right? choose the largest col for all, change the illegal // wrong? </code></pre></td></tr></table></figure>然后就开始想 T2 的 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>c</mi><mo mathvariant="normal">≠</mo><mn>0</mn></mrow><annotation encoding="application/x-tex">c\neq 0</annotation></semantics></math>c=0，希望对正解有启发意义。结果啥也没想出来。最后 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mrow><mo fence="true">[</mo><mn>60</mn><mo separator="true">,</mo><mn>70</mn><mo fence="true">]</mo></mrow><mo>+</mo><mn>40</mn><mo>+</mo><mrow><mo fence="true">[</mo><mn>0</mn><mo separator="true">,</mo><mo stretchy="false">?</mo><mo fence="true">]</mo></mrow><mo>+</mo><mn>8</mn><mo>=</mo><mrow><mo fence="true">[</mo><mn>108</mn><mo separator="true">,</mo><mn>118</mn><mo fence="true">]</mo></mrow></mrow><annotation encoding="application/x-tex">\left[60,70\right]+40+\left[0,?\right]+8=\left[108,118\right]</annotation></semantics></math>[60,70]+40+[0,?]+8=[108,118] 遗憾离场。我是不是要停课了。<h2 id="Day-27">Day -27</h2>2025/11/02北斗已经有 SD 代码了，一看为啥 T1 挂 10pts，T2 还 MLE。为啥我感觉 T1 不简单于编辑字符串啊。为啥说这玩意比廊桥分配简单。这下真要停课了。<h2 id="Day-26">Day -26</h2>2025/11/03凌晨 <code>00:50</code>。躺床上没睡着想 T2，然后突然发现我好像会了。梦中惊坐起，去问 MrPython 做法，发现差不多对了。就在床上深度思考更睡不着了。<h2 id="Day-23-停课">Day -23 停课</h2>2025/11/06停课。<h2 id="Day-19-Day-5-集训">Day -19 ~ Day -5 集训</h2>2025/11/10 ~ 2025/11/24云斗集训，今年感觉还挺好的。打了前四场模拟赛，发现我怎么好多不会的。开始自己做题。<h2 id="Day-4-Day-2">Day -4 ~ Day -2</h2>2025/11/25 ~ 2025/11/27在机房打板子。机房甲流爆发，全天和 cpp xixisuper 苟在讨论室戴口罩。吓人。<h2 id="Day-1">Day -1</h2>2025/11/28出发去淄博，下午到北京路亚朵，在酒店启动打板子模式。打了 tarjan*2+hash*2+sgt*2，顺便把各种 log 数据结构和 lca 打了一遍。楼下吃的熙临居博山菜，感觉很好吃啊。去试机发现还是去年的同一个机房，windows 和虚拟机都有装好插件的 vscode，但是不知道为啥 <code>launch.json</code> 死活配不对，而且还莫名其妙死机一分钟，决定还是用 devcpp 写代码。取模 1s 5.5e8。晚上回到房间开始用 devcpp 随机写东西，结果发现完全不适应，自动补全完全没有，发现 xixisuper 有？？？这还有版本差异。在 22:20 成功清空任务列表，十点半多一点睡觉。<h2 id="Day-0-NOIP">Day 0 NOIP</h2>2025/11/29今年好像没有什么太大的反应了，面对距离退役还有 5 个多小时的事实已经释然了。心态从 06:50 到 12:00 左右都一直非常平静。从酒店一路堵到山理工，罪魁祸首是淄博实验。看人家学校校园还大，门还多，周六 8 点才到校，某学校学学人家。08:07 进场，先把缺省源和目录建好，然后就发压缩包密码了。开 T1，读一遍题发现这不是显然吗？于是乎马上码代码，大概 08:15-20 左右写完，思路大概是尽量多的选 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>x</mi><mo>+</mo><mi>y</mi></mrow><annotation encoding="application/x-tex">x+y</annotation></semantics></math>x+y 最大的，如果实在选不了了就按 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>x</mi></mrow><annotation encoding="application/x-tex">x</annotation></semantics></math>x 排序去选 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>x</mi></mrow><annotation encoding="application/x-tex">x</annotation></semantics></math>x 小的，对于一个 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>x</mi></mrow><annotation encoding="application/x-tex">x</annotation></semantics></math>x 检查撤销上一步 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>x</mi><mo>+</mo><mi>y</mi></mrow><annotation encoding="application/x-tex">x+y</annotation></semantics></math>x+y 那个对的选择是否不劣。大样例 6 没过，输出 81 比答案少 2。不懂为什么，尝试换了个思路写了个暴力错的更离谱了。然后整理了一下发现前半部分选 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>x</mi><mo>+</mo><mi>y</mi></mrow><annotation encoding="application/x-tex">x+y</annotation></semantics></math>x+y 最大的肯定是对的，问题是后面。直接去按 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>x</mi></mrow><annotation encoding="application/x-tex">x</annotation></semantics></math>x 从小到大排序，看如果把一部分 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>x</mi><mo>+</mo><mi>y</mi></mrow><annotation encoding="application/x-tex">x+y</annotation></semantics></math>x+y 的选择换成一个 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>x</mi></mrow><annotation encoding="application/x-tex">x</annotation></semantics></math>x 前缀是否会更优即可。从原来代码删删改改，使用 <code>res</code>, <code>cnt</code>, <code>cntdiff</code>, <code>last</code> 等意义不明的整型变量。大样例过了，开 T2。瞪了一眼觉得仍然是简单题啊，手模样例感觉就是总数减除以二之后产生的逆序对数量。上个厕所冷静一下然后 5min 简单实现发现错完了。决定打暴力，直接 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi mathvariant="normal">Θ</mi><mo stretchy="false">(</mo><msup><mn>2</mn><mi>n</mi></msup><mo>×</mo><mi>n</mi><mi>m</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">\Theta(2^n\times nm)</annotation></semantics></math>Θ(2n×nm)，20pts 到手。开始思考特殊性质，对 A 性质闪过了一个答案为 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><msup><mn>2</mn><mi>n</mi></msup></mrow><annotation encoding="application/x-tex">2^n</annotation></semantics></math>2n，但是因为不会证并且没大样例放弃了。开写 T2 之前看了 T3，一直没想到什么思路。写完 T2 暴力想了两个贪心策略但是一眼假，暴力实现难度略高。看 T4 的简单题意感觉暴力可做。然后就不知道怎么打出来了忘了是 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi mathvariant="normal">Θ</mi><mo stretchy="false">(</mo><msup><mi>n</mi><mn>3</mn></msup><mi>log</mi><mo>⁡</mo><mi>n</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">\Theta(n^3\log n)</annotation></semantics></math>Θ(n3logn) 还是 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi mathvariant="normal">Θ</mi><mo stretchy="false">(</mo><msup><mi>n</mi><mn>2</mn></msup><mi>log</mi><mo>⁡</mo><mi>n</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">\Theta(n^2\log n)</annotation></semantics></math>Θ(n2logn) 复杂度的暴力了，总之期望得分 5pts。甚至取模都没想到是 <code>unsigned long long</code> 直接用的 <code>__int128</code>。回到 T2，突然发现有贡献当且仅当两个 1 合并起来比 2 要小，然后就不会做了。最后 20-30min 比较辗转反侧，再多打一个 T3 暴力显然来不及，想任何一个题正解也想不完。在 T4 的文件末尾写下了：<figure class="highlight cpp"><table><tr><td class="gutter"><pre>1 </pre></td><td class="code"><pre><code class="hljs cpp">// AFOed on 20251129 </code></pre></td></tr></table></figure>13:00 出场。下楼看见 xixisuper，直接问 T2 做出来了吗，T3 做出来了吗，T4 做出来了吗。他一脸懵逼说不会啊，不会啊，不会啊。于是去机房群里激情开喷。山理工路上碰到 cpp，问她 T2 会做吗，得到了一样的答案。群里伪人和 MrPython 自称全都不会。大家全都开始在群里激情开喷。<img src="https://img.makerlife.top/data/202511292229517.png" alt="激情开喷">但是某文化课了两个周的哥们会？？？直接场切紫题？折磨牛。结果在群里对 T1 大家思路全都不一样。对 T2 发现少拿 4pts。对 T4 发现暴力打丑了。自认为 T1 思路很对。洛谷是黄黑黑黑？黄嘿嘿嘿。下午直接回家，想测洛谷的 T1 民间数据。此时看到群里发了一个大样例全过洛谷得 80pts 的截图。打了一会 T1 打不动了，大脑停止工作。但是发现我考场代码好像按 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>x</mi><mo>+</mo><mi>y</mi></mrow><annotation encoding="application/x-tex">x+y</annotation></semantics></math>x+y 排序的时候没有考虑有多组 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>x</mi><mo>+</mo><mi>y</mi></mrow><annotation encoding="application/x-tex">x+y</annotation></semantics></math>x+y 相同处理 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>x</mi></mrow><annotation encoding="application/x-tex">x</annotation></semantics></math>x 的情况。这下要随机挂分了。算了一下期望 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>100</mn><mo>+</mo><mn>20</mn><mo>+</mo><mn>0</mn><mo>+</mo><mn>5</mn><mo>=</mo><mn>125</mn></mrow><annotation encoding="application/x-tex">100+20+0+5=125</annotation></semantics></math>100+20+0+5=125，就看 T1 挂不挂了。AFO 还是很平静的。甚至以为第二天就要上学了，过单休过习惯了。我还是舍不得我的 oi 啊。

微积分学习笔记

Makerlife 的小站

Makerlife

2025年10月2日 10:27

极限与导数

A：在海里游泳，获得幸福度 $a _ i$ 。
B：在山上抓虫，获得幸福度 $b _ i$ 。
C：在家做作业，获得幸福度 $c _ i$ 。

不能连续两天以上做同样的活动，计算最大总幸福度。

DP 板子题。设 $f_{i,j}$ 表示截止到第 $i$ 天时做第 $j$ 件事的幸福值总和。

则易得转移方程为：

$f_{i,1}=\max(f_{i-1,2},f_{i-1,3})\\f_{i,2}=\max(f_{i-1,1},f_{i-1,3})\\f_{i,3}=\max(f_{i-1,1},f_{i-1,2})$

Core Code:

for(int i=1;i<=n;i++)
{
f[i][1]=max(f[i-1][2],f[i-1][3])+a[i];
f[i][2]=max(f[i-1][1],f[i-1][3])+b[i];
f[i][3]=max(f[i-1][1],f[i-1][2])+c[i];
}

AT_DP_K Stones

洛谷 link

▶

题意

$N$ 个正整数组成的集合 $A = \{ a _ 1, a _ 2, \ldots, a _ N \}$ 。太郎君和次郎君将用以下游戏进行对决。

首先，准备一个有 $K$ 个石子的堆。两人依次进行以下操作。太郎君先手。

从集合 $A$ 中选择一个元素 $x$ ，从石堆中恰好移除 $x$ 个石子。

不能进行操作的人输掉游戏。当两人都按照最优策略行动时，判断谁会获胜。

显然当一名玩家操作完成后石子数量为 $0$ ，则这名玩家必胜。

设 $f_i$ 表示剩余 $i$ 枚石子当前操作的人的输赢情况 ( $1/0$ )，可以发现当且仅当当前操作的上一步操作必输，当前操作才可以必胜，即如果有 $a_j$ 使得 $f_{i-a_j}=0$ ，则 $f_i=1$ 。

初始化 $f_0=0$ ，则有：

$f_i=\begin{cases}1,&a_j\leq i,f_{i-a_j}=0\\0 ,& \text{otherwise.}\end{cases}$

Core Code:

f[0]=0;
for(int i=1;i<=k;i++)
{
for(int j=1;j<=n;j++)
{
if(i-a[j]>=0 && !f[i-a[j]]) f[i]=1;
}
}

AT_DP_M Candies

link

tag: 背包 DP, 前缀和

$K$ 颗糖分给 $n$ 个人，第 $i$ 个人至少分得 $0$ 颗，至多分得 $a_i$ 颗，必须分完，求方案数，答案对 $10^9+7$ 取模。

类似背包的处理思路，设 $f_{i,j}$ 表示第 $i$ 个人分完后已经分了 $j$ 个糖，它可以由上一步的 $(j-a_i)\sim j$ 转移得到，所以

$f_{i,j}=\sum^j_{k=\max(0,j-a_i)}f_{i-1,k}$

考虑优化时间，滚动数组不可行。发现每一个 $i$ 对应的值都由 $i-1$ 中连续一段的值转移而来，想到用滚动的前缀和维护 $i-1$ 的所有 $f$ 值。

Code:

int calc(int l,int r) {
    if(l==0) return sum[r];
    return sum[r]-sum[l-1];
}
int main() {
    f[0][0]=1;
    for(int i=1;i<=n;i++) {
        sum[0]=f[i-1][0];
        for(int j=1;j<=m;j++) {
            sum[j]=(sum[j-1]+f[i-1][j]+mod)%mod;
        }
        for(int j=0;j<=m;j++) {
            f[i][j]=(calc(max(0ll,j-a[i]),j)+mod)%mod;
        }
    }
    printf("%lld\n",f[n][m]%mod);
}

AT_DP_P Independent Set

link

tag: 树形 DP

给一棵树，每一个点可以染成黑色或白色，任意两个相邻节点不能都是黑色，求方案数。

设 $f_{u,0/1}$ 表示 $u$ 节点染成 W/B 颜色时的方案数。DFS 子树的方案数，可以得到：

$\begin{aligned}f_{u,0}&=\prod_{v\in u}(f_{v,0}+f_{v,1})\\f_{u,1}&=\prod_{v\in u}f_{v,0}\end{aligned}$

注意 $1$ 号点为根，输入无序需建双向边。

Code:

void dfs(int u) {
    g.vis[u]=1;
    f[u][0]=f[u][1]=1;
    for(int i=0;i<e[u].size();i++) {
        int v=e[u][i];
        if(!g.vis[v]) {
            dfs(v);
            f[u][0]=(f[u][0]*(f[v][0]+f[v][1]))%mod;
            f[u][1]=(f[u][1]*f[v][0])%mod;
        }
    }
}

AT_DP_Q Flowers

link

有一排花，共 $n$ 个，第 $i$ 个的高度是 $h_i$ ，权值是 $a_i$ ，保证高度互不相同。现在拿走一些花，使剩下的花高度单调递增，问剩下的花权值之和最大是多少。

tag: 线段树优化 DP

带权的最长上升子序列，设 $f_i$ 表示第 $i$ 个元素结尾的最大答案，可以参照最长上升子序列写出转移方程

$f_{i}=\max_{j=1}^{i-1}\{f_{j}|h_j<h_i\}+a_{i}$

考虑优化，观察到转移方程是区间最大值，想到用值域线段树优化。将 $h_i$ 作为线段树的下标，对应当前高度时的 $f_i$ 。

struct node {
    ll val;
}t[N * 4];
struct tree {
    void pushup(int p) {
        t[p].val = max(t[p * 2].val, t[p * 2 + 1].val);
    }
    void modify(int p, int l, int r, int x, ll k) {
        if (l == r) {
            t[p].val = k;
            return;
        }
        int mid = (l + r) >> 1;
        if (x <= mid) modify(p * 2, l, mid, x, k);
        else modify(p * 2 + 1, mid + 1, r, x, k);
        pushup(p);
    }
    ll query(int p, int l, int r, int x, int y) {
        if (x <= l && r <= y) {
            return t[p].val;
        }
        ll res = 0;
        int mid = (l + r) >> 1;
        if (x <= mid) res = max(res, query(p * 2, l, mid, x, y));
        if (y >= mid + 1) res = max(res, query(p * 2 + 1, mid + 1, r, x, y));
        return res;
    }
}sgt;
int main() {
    n = read();
    for (int i = 1; i <= n; i++) {
        h[i] = read();
    }
    for (int i = 1; i <= n; i++) {
        a[i] = read();
    }
    for (int i = 1; i <= n; i++) {
        f[i] = sgt.query(1, 1, n, 1, h[i]) + a[i];
        sgt.modify(1, 1, n, h[i], f[i]);
    }
    cout << sgt.query(1, 1, n, 1, n) << endl;
    return 0;
}

AT_DP_T Permutation

link

有一个长为 $N$ 的正整数排列。给定一个由 < 和 > 组成长为 $N-1$ 的的字符串。对于任意满足 $1 \le i \le N-1$ 的字符 $s_i$ ，如果 $s_i$ 是 < 则 $P_i<P_{i+1}$ 、如果 $s_i$ 是 > 则 $P_i>P_{i+1}$ 。求满足这样的性质的排列 $P$ 的方案数。

由于 $p$ 是排列，我们不在意 $p$ 中到底放了什么数，只需要关注当前一步放的数和上一步放的数的大小关系。可以得到状态 $f_{i, j}$ 表示前 $i$ 个数形成的排列中，第 $i$ 个数是第 $j$ 大的方案数。

在转移时，若当前填的数需大于前一个数，那么直接得到 $f_i=\sum_{k=1}^{j-1}f_{i-1,k}$ 。

若小于前一个数，可以将 $p_1\sim p_{i-1}$ 中 $\geq j$ 的数全部加 $1$ ，保证组成的是排列，这等价于遍历的排名 $k$ 都减一（自行手玩样例）， $f_{i}=\sum_{k=j}^{i-1}f_{i-1,k}$ 。

注意到转移是求连续一段的和，前缀和优化即可。

f[1][1] = 1;
for (int i = 1; i <= n; i++) {
    sum[i][1] = 1;
}
for (int i = 2; i <= n; i++) {
    for (int j = 1; j <= i; j++) {
        if(s[i-1] == '>') {
            f[i][j] = (f[i][j] + sum[i-1][i-1] - sum[i-1][j-1] + mod) % mod;
        } else {
            f[i][j] = (f[i][j] + sum[i-1][j-1] + mod) % mod;
        }
        sum[i][j] = (sum[i][j-1] + f[i][j] + mod) % mod;
    }
}
int ans = 0;
for (int i = 1; i <= n; i++) {
    ans = (ans + f[n][i] + mod) % mod;
}

TDPC_IWI イウィ

洛谷 link

tag: 区间 DP

给定一个仅由字符 $\texttt{i}$ 和 $\texttt{w}$ 构成的字符串 $s$ 。你可以进行若干次操作，每次从串中选取连续的三个字符 $\texttt{iwi}$ 并删除；每次操作后这三个字符的左侧和右侧会连接在一起，得到一个长度比原来小 $3$ 的新串。求可能的最大操作次数。

区间 DP，类似合并石子。

我们定义 $f_{i,j}$ 记录 $i$ 到 $j$ 能删掉多少字符，显然最后答案应除以 $3$ 。

因为答案计算的是最大的步数，那么对于一个大区间，在一般情况下的答案就应该是其分成的两个小区间的答案之和。考虑枚举这两个区间之间的分界点 $k$ ，答案取最大值即可。

本题还需要特判一种特殊情况。如果 $s_i$ 和 $s_j$ 为 i， $s_k$ 为 w，且中间的两个小段可以被完全删除。那么，当中间的被删掉之后，左右的 i 和中间的 w 就会拼在一起，也可以删掉，那么这个区间的答案就应该是它的长度，但显然直接相加有可能会出错。

Core Code:

for(int a=2;a<=len;a++)
{
for(int i=1;a+i-1<=len;i++)
{
int j=a+i-1;
for(int k=i;k<j;k++)
{
f[i][j]=max(f[i][j],f[i][k]+f[k+1][j]);
if(s[i]=='i' && s[j]=='i' && s[k]=='w' && f[i+1][k-1] == k-i-1 && f[k+1][j-1] == j-1-k)
{
f[i][j]=j-i+1;
}
}
}
}
write(f[1][len]/3);

ABC247F Cards

并查集，待填坑。

ABC336D Pyramid

link

▶

题意

对于正整数 $k$ ，一个大小为 $k$ 的“金字塔数列”为一个长度为 $2k-1$ 的数列，里面的数字依次为 $1,2,3,\dots k-1,k,k-1,\dots 3,2,1$ 。
现在给一个长度为 $n$ 的数列 $S$ ，你可以进行以下操作任意次，使得数列最后变为一个“金字塔数列”：

选择一个数 $i(1 \le i \le n)$ ，把 $S_i$ 减少 $1$ 。
删除整个数列的第一个或最后一个数字。

问最后生成的“金字塔数列”的最大的 $k$ 是多少。

显然一个金字塔数列是由左右两部分拼接而成的。设 $f_{i}$ 表示前 $i$ 个数能组成左半部分的最长长度， $g_{i}$ 表示以 $i$ 为首的序列能组成右半部分的最长长度（差不多等价于后 $i$ 个数，但注意转移方程的写法）。一个明显的性质是如果满足可以构成长度为 $x$ 的序列，那么一定可以通过删掉元素构成长度为 $x-1$ 的序列，所以可以发现以 $i$ 为中间项的最长长度即为 $\min\{f_i, g_i\}$ 。

以 $f$ 为例，假设 $s_i$ 的所有值都是 $+\infty$ ，可以得到显然的转移方程 $f_{i}=f_{i-1}+1$ 。如果加上 $s_i$ 的限制条件，那么 $f_i=\min\{f_{i-1}+1, s_i\}$ 。同理可得 $g_i=\min\{g_{i+1}+1, s_i\}$ 。

n = read();
for (int i = 1; i <= n; i++) {
    a[i] = read();
}
f[1] = g[n] = 1;
for (int i = 2; i <= n; i++) {
    f[i] = min(f[i-1] + 1, a[i]);
}
for (int i = n - 1; i >= 1; i--) {
    g[i] = min(g[i+1] + 1, a[i]);
}
int ans = 0;
for (int i = 1; i <= n; i++) {
    ans = max(ans, min(f[i], g[i]));
}
cout << ans << endl;

数论学习笔记

Makerlife 的小站

Makerlife

2024年6月27日 09:24

<h2 id="欧几里得算法">欧几里得算法</h2>就是求最大公约数的辗转相除法。<h3 id="数学公式">数学公式</h3><math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mi>gcd</mi><mo>⁡</mo><mo stretchy="false">(</mo><mi>a</mi><mo separator="true">,</mo><mi>b</mi><mo stretchy="false">)</mo><mo>=</mo><mrow><mo fence="true">{</mo><mtable rowspacing="0.36em" columnalign="left left" columnspacing="1em"><mtr><mtd><mstyle scriptlevel="0" displaystyle="false"><mrow><mi>gcd</mi><mo>⁡</mo><mo stretchy="false">(</mo><mi>b</mi><mo separator="true">,</mo><mi>a</mi><mtext> </mtext><mo lspace="0.22em" rspace="0.22em"><mrow><mi mathvariant="normal">m</mi><mi mathvariant="normal">o</mi><mi mathvariant="normal">d</mi></mrow></mo><mtext> </mtext><mi>b</mi><mo stretchy="false">)</mo></mrow></mstyle></mtd><mtd><mstyle scriptlevel="0" displaystyle="false"><mrow><mo separator="true">,</mo><mi>b</mi><mo mathvariant="normal">≠</mo><mn>0</mn></mrow></mstyle></mtd></mtr><mtr><mtd><mstyle scriptlevel="0" displaystyle="false"><mi>a</mi></mstyle></mtd><mtd><mstyle scriptlevel="0" displaystyle="false"><mrow><mo separator="true">,</mo><mi>b</mi><mo>=</mo><mn>0</mn></mrow></mstyle></mtd></mtr></mtable></mrow></mrow><annotation encoding="application/x-tex">\gcd(a, b)=\begin{cases}\gcd(b,a\bmod b) &,b\neq 0\\a &,b=0\end{cases}</annotation></semantics></math>gcd(a,b)={gcd(b,amodb)a,b=0,b=0<h3 id="模板">模板</h3><figure class="highlight cpp"><table><tr><td class="gutter"><pre>1 2 3 4 5 </pre></td><td class="code"><pre><code class="hljs cpp">int gcd(int a,int b) { if(b==0) return a; return gcd(b,a%b); } </code></pre></td></tr></table></figure><h2 id="拓展欧几里得-exgcd">拓展欧几里得(exgcd)</h2><h3 id="适用问题">适用问题</h3>给定正整数 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>a</mi><mo separator="true">,</mo><mi>b</mi></mrow><annotation encoding="application/x-tex">a,b</annotation></semantics></math>a,b，求出 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>a</mi><mi>x</mi><mo>+</mo><mi>b</mi><mi>y</mi><mo>=</mo><mi>gcd</mi><mo>⁡</mo><mo stretchy="false">(</mo><mi>a</mi><mo separator="true">,</mo><mi>b</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">ax+by=\gcd(a,b)</annotation></semantics></math>ax+by=gcd(a,b) 的一组正整数解。<h3 id="算法思路">算法思路</h3>由欧几里得算法得出 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>a</mi><mi>x</mi><mo>+</mo><mi>b</mi><mi>y</mi><mo>=</mo><mi>gcd</mi><mo>⁡</mo><mo stretchy="false">(</mo><mi>a</mi><mo separator="true">,</mo><mi>b</mi><mo stretchy="false">)</mo><mo>=</mo><mi>gcd</mi><mo>⁡</mo><mo stretchy="false">(</mo><mi>b</mi><mo separator="true">,</mo><mi>a</mi><mtext> </mtext><mo lspace="0.22em" rspace="0.22em"><mrow><mi mathvariant="normal">m</mi><mi mathvariant="normal">o</mi><mi mathvariant="normal">d</mi></mrow></mo><mtext> </mtext><mi>b</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">ax+by=\gcd(a,b)=\gcd(b,a\bmod b)</annotation></semantics></math>ax+by=gcd(a,b)=gcd(b,amodb)，代回原式，即为：<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mi>b</mi><msup><mi>x</mi><mo mathvariant="normal" lspace="0em" rspace="0em">′</mo></msup><mo>+</mo><mi>a</mi><mtext> </mtext><mo lspace="0.22em" rspace="0.22em"><mrow><mi mathvariant="normal">m</mi><mi mathvariant="normal">o</mi><mi mathvariant="normal">d</mi></mrow></mo><mtext> </mtext><mi>b</mi><mo>×</mo><msup><mi>y</mi><mo mathvariant="normal" lspace="0em" rspace="0em">′</mo></msup><mo>=</mo><mi>gcd</mi><mo>⁡</mo><mo stretchy="false">(</mo><mi>b</mi><mo separator="true">,</mo><mi>a</mi><mtext> </mtext><mo lspace="0.22em" rspace="0.22em"><mrow><mi mathvariant="normal">m</mi><mi mathvariant="normal">o</mi><mi mathvariant="normal">d</mi></mrow></mo><mtext> </mtext><mi>b</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">bx^{\prime}+a\bmod b\times y^{\prime}=\gcd(b,a\bmod b)</annotation></semantics></math>bx′+amodb×y′=gcd(b,amodb)假设我们已知上式的一组解 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><msup><mi>x</mi><mo mathvariant="normal" lspace="0em" rspace="0em">′</mo></msup><mo separator="true">,</mo><msup><mi>y</mi><mo mathvariant="normal" lspace="0em" rspace="0em">′</mo></msup></mrow><annotation encoding="application/x-tex">x^{\prime},y^{\prime}</annotation></semantics></math>x′,y′，可以得到：<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mtable rowspacing="0.25em" columnalign="right left" columnspacing="0em"><mtr><mtd><mstyle scriptlevel="0" displaystyle="true"><mrow><mi>a</mi><mi>x</mi><mo>+</mo><mi>b</mi><mi>y</mi><mo>=</mo><mi>gcd</mi><mo>⁡</mo><mo stretchy="false">(</mo><mi>a</mi><mo separator="true">,</mo><mi>b</mi><mo stretchy="false">)</mo></mrow></mstyle></mtd><mtd><mstyle scriptlevel="0" displaystyle="true"><mrow><mrow></mrow><mo>=</mo><mi>b</mi><msup><mi>x</mi><mo mathvariant="normal" lspace="0em" rspace="0em">′</mo></msup><mo>+</mo><mi>a</mi><mtext> </mtext><mo lspace="0.22em" rspace="0.22em"><mrow><mi mathvariant="normal">m</mi><mi mathvariant="normal">o</mi><mi mathvariant="normal">d</mi></mrow></mo><mtext> </mtext><mi>b</mi><mo>×</mo><msup><mi>y</mi><mo mathvariant="normal" lspace="0em" rspace="0em">′</mo></msup></mrow></mstyle></mtd></mtr><mtr><mtd><mstyle scriptlevel="0" displaystyle="true"><mrow></mrow></mstyle></mtd><mtd><mstyle scriptlevel="0" displaystyle="true"><mrow><mrow></mrow><mo>=</mo><mi>b</mi><msup><mi>x</mi><mo mathvariant="normal" lspace="0em" rspace="0em">′</mo></msup><mo>+</mo><mo stretchy="false">(</mo><mi>a</mi><mo>−</mo><mo stretchy="false">⌊</mo><mfrac><mi>a</mi><mi>b</mi></mfrac><mo stretchy="false">⌋</mo><mo>×</mo><mi>b</mi><mo stretchy="false">)</mo><msup><mi>y</mi><mo mathvariant="normal" lspace="0em" rspace="0em">′</mo></msup></mrow></mstyle></mtd></mtr><mtr><mtd><mstyle scriptlevel="0" displaystyle="true"><mrow></mrow></mstyle></mtd><mtd><mstyle scriptlevel="0" displaystyle="true"><mrow><mrow></mrow><mo>=</mo><mi>a</mi><msup><mi>y</mi><mo mathvariant="normal" lspace="0em" rspace="0em">′</mo></msup><mo>+</mo><mi>b</mi><mo stretchy="false">(</mo><msup><mi>x</mi><mo mathvariant="normal" lspace="0em" rspace="0em">′</mo></msup><mo>−</mo><mo stretchy="false">⌊</mo><mfrac><mi>a</mi><mi>b</mi></mfrac><mo stretchy="false">⌋</mo><mo>×</mo><msup><mi>y</mi><mo mathvariant="normal" lspace="0em" rspace="0em">′</mo></msup><mo stretchy="false">)</mo></mrow></mstyle></mtd></mtr></mtable><annotation encoding="application/x-tex">\begin{aligned}ax+by=\gcd(a, b) &=b x^{\prime}+a \bmod b\times y^{\prime} \\&=b x^{\prime}+(a-\lfloor \frac{a}{b} \rfloor \times b) y^{\prime}\\&=a y^{\prime}+b(x^{\prime}-\lfloor \frac{a}{b}\rfloor \times y^{\prime})\end{aligned}</annotation></semantics></math>ax+by=gcd(a,b)=bx′+amodb×y′=bx′+(a−⌊ba⌋×b)y′=ay′+b(x′−⌊ba⌋×y′)所以<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mtable rowspacing="0.25em" columnalign="right left" columnspacing="0em"><mtr><mtd><mstyle scriptlevel="0" displaystyle="true"><mrow><mi>a</mi><mi>x</mi><mo>+</mo><mi>b</mi><mi>y</mi></mrow></mstyle></mtd><mtd><mstyle scriptlevel="0" displaystyle="true"><mrow><mrow></mrow><mo>=</mo><mi>a</mi><msup><mi>y</mi><mo mathvariant="normal" lspace="0em" rspace="0em">′</mo></msup><mo>+</mo><mi>b</mi><mo stretchy="false">(</mo><msup><mi>x</mi><mo mathvariant="normal" lspace="0em" rspace="0em">′</mo></msup><mo>−</mo><mo stretchy="false">⌊</mo><mfrac><mi>a</mi><mi>b</mi></mfrac><mo stretchy="false">⌋</mo><mo>×</mo><msup><mi>y</mi><mo mathvariant="normal" lspace="0em" rspace="0em">′</mo></msup><mo stretchy="false">)</mo></mrow></mstyle></mtd></mtr><mtr><mtd><mstyle scriptlevel="0" displaystyle="true"><mi>x</mi></mstyle></mtd><mtd><mstyle scriptlevel="0" displaystyle="true"><mrow><mrow></mrow><mo>=</mo><msup><mi>y</mi><mo mathvariant="normal" lspace="0em" rspace="0em">′</mo></msup></mrow></mstyle></mtd></mtr><mtr><mtd><mstyle scriptlevel="0" displaystyle="true"><mi>y</mi></mstyle></mtd><mtd><mstyle scriptlevel="0" displaystyle="true"><mrow><mrow></mrow><mo>=</mo><msup><mi>x</mi><mo mathvariant="normal" lspace="0em" rspace="0em">′</mo></msup><mo>−</mo><mfrac><mi>a</mi><mi>b</mi></mfrac><mo>×</mo><msup><mi>y</mi><mo mathvariant="normal" lspace="0em" rspace="0em">′</mo></msup></mrow></mstyle></mtd></mtr></mtable><annotation encoding="application/x-tex">\begin{aligned}ax+by&=ay^{\prime}+b(x^{\prime}-\lfloor \frac{a}{b}\rfloor \times y^{\prime})\\x&=y^{\prime}\\y&=x^{\prime}-\frac{a}{b}\times y^{\prime}\end{aligned}</annotation></semantics></math>ax+byxy=ay′+b(x′−⌊ba⌋×y′)=y′=x′−ba×y′我们发现，当 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>b</mi><mo>=</mo><mn>0</mn></mrow><annotation encoding="application/x-tex">b=0</annotation></semantics></math>b=0 时，<math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>a</mi><mo>×</mo><mn>1</mn><mo>+</mo><mi>b</mi><mo>×</mo><mn>0</mn><mo>=</mo><mi>a</mi></mrow><annotation encoding="application/x-tex">a\times 1+b\times 0=a</annotation></semantics></math>a×1+b×0=a，有一组解<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mo fence="true">{</mo><mtable rowspacing="0.36em" columnalign="left left" columnspacing="1em"><mtr><mtd><mstyle scriptlevel="0" displaystyle="false"><mrow><mi>x</mi><mo>=</mo><mn>1</mn></mrow></mstyle></mtd></mtr><mtr><mtd><mstyle scriptlevel="0" displaystyle="false"><mrow><mi>y</mi><mo>=</mo><mn>0</mn></mrow></mstyle></mtd></mtr></mtable></mrow><annotation encoding="application/x-tex">\begin{cases}x=1\\y=0\end{cases}</annotation></semantics></math>{x=1y=0<h3 id="模板-2">模板</h3>直接递归求解即可<figure class="highlight cpp"><table><tr><td class="gutter"><pre>1 2 3 4 5 6 7 8 9 10 11 12 </pre></td><td class="code"><pre><code class="hljs cpp">int exgcd(int a,int b,int &x,int &y) { if(b==0) { x=1; y=0; return a; } int g=exgcd(b,a%b,y,x); y=y-a/b*x; return g; } </code></pre></td></tr></table></figure>这时，我们已经得到了一组解，下一步是求解 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>a</mi><mi>x</mi><mo>+</mo><mi>b</mi><mi>y</mi><mo>=</mo><mi>c</mi></mrow><annotation encoding="application/x-tex">ax+by=c</annotation></semantics></math>ax+by=c。<h3 id="求解-ax-by-c">求解 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>a</mi><mi>x</mi><mo>+</mo><mi>b</mi><mi>y</mi><mo>=</mo><mi>c</mi></mrow><annotation encoding="application/x-tex">ax+by=c</annotation></semantics></math>ax+by=c</h3>接下来我们需要分类讨论。设 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>g</mi><mo>=</mo><mi>gcd</mi><mo>⁡</mo><mo stretchy="false">(</mo><mi>a</mi><mo separator="true">,</mo><mi>b</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">g=\gcd(a,b)</annotation></semantics></math>g=gcd(a,b)。当 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>c</mi><mtext> </mtext><mo lspace="0.22em" rspace="0.22em"><mrow><mi mathvariant="normal">m</mi><mi mathvariant="normal">o</mi><mi mathvariant="normal">d</mi></mrow></mo><mtext> </mtext><mi>b</mi><mo mathvariant="normal">≠</mo><mn>0</mn></mrow><annotation encoding="application/x-tex">c\bmod b\neq0</annotation></semantics></math>cmodb=0 时，无解。否则，令 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>k</mi><mo>=</mo><mfrac><mi>c</mi><mi>g</mi></mfrac></mrow><annotation encoding="application/x-tex">k=\frac{c}{g}</annotation></semantics></math>k=gc，则<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mi>a</mi><msup><mi>x</mi><mo mathvariant="normal" lspace="0em" rspace="0em">′</mo></msup><mi>k</mi><mo>+</mo><mi>b</mi><msup><mi>y</mi><mo mathvariant="normal" lspace="0em" rspace="0em">′</mo></msup><mi>k</mi><mo>=</mo><mi>g</mi><mo>×</mo><mi>k</mi><mo>=</mo><mi>c</mi></mrow><annotation encoding="application/x-tex">ax^{\prime}k+by^{\prime}k=g\times k=c</annotation></semantics></math>ax′k+by′k=g×k=c得<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mo fence="true">{</mo><mtable rowspacing="0.36em" columnalign="left left" columnspacing="1em"><mtr><mtd><mstyle scriptlevel="0" displaystyle="false"><mrow><mi>x</mi><mo>=</mo><msup><mi>x</mi><mo mathvariant="normal" lspace="0em" rspace="0em">′</mo></msup><mi>k</mi></mrow></mstyle></mtd></mtr><mtr><mtd><mstyle scriptlevel="0" displaystyle="false"><mrow><mi>y</mi><mo>=</mo><msup><mi>y</mi><mo mathvariant="normal" lspace="0em" rspace="0em">′</mo></msup><mi>k</mi></mrow></mstyle></mtd></mtr></mtable></mrow><annotation encoding="application/x-tex">\begin{cases}x=x^{\prime}k\\y=y^{\prime}k\end{cases}</annotation></semantics></math>{x=x′ky=y′k设 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>x</mi></mrow><annotation encoding="application/x-tex">x</annotation></semantics></math>x 的周期 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>T</mi><mo>=</mo><mfrac><mi>b</mi><mi>g</mi></mfrac></mrow><annotation encoding="application/x-tex">T=\frac{b}{g}</annotation></semantics></math>T=gb，则最小正整数解为 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mo stretchy="false">(</mo><mi>x</mi><mtext> </mtext><mo lspace="0.22em" rspace="0.22em"><mrow><mi mathvariant="normal">m</mi><mi mathvariant="normal">o</mi><mi mathvariant="normal">d</mi></mrow></mo><mtext> </mtext><mi>T</mi><mo>+</mo><mi>T</mi><mo stretchy="false">)</mo><mtext> </mtext><mo lspace="0.22em" rspace="0.22em"><mrow><mi mathvariant="normal">m</mi><mi mathvariant="normal">o</mi><mi mathvariant="normal">d</mi></mrow></mo><mtext> </mtext><mi>T</mi></mrow><annotation encoding="application/x-tex">(x\bmod T+T)\bmod T</annotation></semantics></math>(xmodT+T)modT。<h2 id="乘法逆元">乘法逆元</h2><h3 id="定义">定义</h3>已知 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>a</mi><mo separator="true">,</mo><mi>p</mi></mrow><annotation encoding="application/x-tex">a,p</annotation></semantics></math>a,p，求 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>a</mi><mi>x</mi><mo>≡</mo><mn>1</mn><mspace></mspace><mspace width="0.4444em"/><mo stretchy="false">(</mo><mrow><mi mathvariant="normal">m</mi><mi mathvariant="normal">o</mi><mi mathvariant="normal">d</mi></mrow><mspace width="0.3333em"/><mi>p</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">ax\equiv 1\pmod{p}</annotation></semantics></math>ax≡1(modp) 中的 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>x</mi></mrow><annotation encoding="application/x-tex">x</annotation></semantics></math>x，称 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>x</mi></mrow><annotation encoding="application/x-tex">x</annotation></semantics></math>x 为 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>a</mi></mrow><annotation encoding="application/x-tex">a</annotation></semantics></math>a 关于 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>p</mi></mrow><annotation encoding="application/x-tex">p</annotation></semantics></math>p 的逆元。<h3 id="求解">求解</h3>直接求解 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>a</mi><mi>x</mi><mo>+</mo><mi>p</mi><mi>y</mi><mo>=</mo><mn>1</mn></mrow><annotation encoding="application/x-tex">ax+py=1</annotation></semantics></math>ax+py=1 即可。最终答案为 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mo stretchy="false">(</mo><mi>x</mi><mtext> </mtext><mo lspace="0.22em" rspace="0.22em"><mrow><mi mathvariant="normal">m</mi><mi mathvariant="normal">o</mi><mi mathvariant="normal">d</mi></mrow></mo><mtext> </mtext><mi>p</mi><mo>+</mo><mi>p</mi><mo stretchy="false">)</mo><mtext> </mtext><mo lspace="0.22em" rspace="0.22em"><mrow><mi mathvariant="normal">m</mi><mi mathvariant="normal">o</mi><mi mathvariant="normal">d</mi></mrow></mo><mtext> </mtext><mi>p</mi></mrow><annotation encoding="application/x-tex">(x\bmod p+p)\bmod p</annotation></semantics></math>(xmodp+p)modp。<h2 id="费马小定理">费马小定理</h2>当 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>p</mi></mrow><annotation encoding="application/x-tex">p</annotation></semantics></math>p 为素数时，<math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>a</mi></mrow><annotation encoding="application/x-tex">a</annotation></semantics></math>a 关于 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>p</mi></mrow><annotation encoding="application/x-tex">p</annotation></semantics></math>p 的逆元是 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><msup><mi>a</mi><mrow><mi>p</mi><mo>−</mo><mn>2</mn></mrow></msup></mrow><annotation encoding="application/x-tex">a^{p-2}</annotation></semantics></math>ap−2。<h2 id="数论分块">数论分块</h2>balabala<math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>a</mi><mtext> </mtext><mo lspace="0.22em" rspace="0.22em"><mrow><mi mathvariant="normal">m</mi><mi mathvariant="normal">o</mi><mi mathvariant="normal">d</mi></mrow></mo><mtext> </mtext><mi>b</mi><mo>=</mo><mi>a</mi><mo>−</mo><mi>b</mi><mo>×</mo><mo stretchy="false">⌊</mo><mfrac><mi>a</mi><mi>b</mi></mfrac><mo stretchy="false">⌋</mo></mrow><annotation encoding="application/x-tex">a\bmod b=a-b\times\lfloor\frac{a}{b}\rfloor</annotation></semantics></math>amodb=a−b×⌊ba⌋<h2 id="一些题">一些题</h2><h3 id="P1516-青蛙的约会">P1516 青蛙的约会</h3><a href="https://www.luogu.com.cn/problem/P1516">Problem Link</a>这是一道比较裸的拓欧题。<figure class="highlight cpp"><table><tr><td class="gutter"><pre>1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 </pre></td><td class="code"><pre><code class="hljs cpp">#define int ll int x,y,m,n,l; int p,q; int exgcd(int a,int b,int &x,int &y) { if(b==0) { x=1; y=0; return a; } int g=exgcd(b,a%b,y,x); y=y-a/b*x; return g; } signed main() { x=read();y=read();m=read();n=read();l=read(); int a=n-m,b=x-y; if(a<0) { a=-a; b=-b; } int ans=exgcd(a,l); if(b%ans!=0) { cout<<"Impossible"<<endl; } else { cout<<((p*(b/ans))%(l/ans)+l/ans)%(l/ans)<<endl; } return 0; } </code></pre></td></tr></table></figure><h3 id="CF1114C-Trailing-Loves">CF1114C Trailing Loves</h3>首先从 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>10</mn></mrow><annotation encoding="application/x-tex">10</annotation></semantics></math>10 进制开始分析。求 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>p</mi></mrow><annotation encoding="application/x-tex">p</annotation></semantics></math>p 末尾 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>0</mn></mrow><annotation encoding="application/x-tex">0</annotation></semantics></math>0 的数量即为求 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>p</mi></mrow><annotation encoding="application/x-tex">p</annotation></semantics></math>p 的因数中含有 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>2</mn></mrow><annotation encoding="application/x-tex">2</annotation></semantics></math>2 和 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>5</mn></mrow><annotation encoding="application/x-tex">5</annotation></semantics></math>5 的数量的最小值。例如设 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><msub><mi>x</mi><mn>1</mn></msub><mo>=</mo><msup><mn>2</mn><mn>3</mn></msup><mo>×</mo><msup><mn>5</mn><mn>2</mn></msup></mrow><annotation encoding="application/x-tex">x_1=2^3\times 5^2</annotation></semantics></math>x1=23×52，则 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><msub><mi>x</mi><mn>1</mn></msub></mrow><annotation encoding="application/x-tex">x_1</annotation></semantics></math>x1 的末尾 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>0</mn></mrow><annotation encoding="application/x-tex">0</annotation></semantics></math>0 的数量即为 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>min</mi><mo>⁡</mo><mo stretchy="false">(</mo><mn>3</mn><mo separator="true">,</mo><mn>2</mn><mo stretchy="false">)</mo><mo>=</mo><mn>2</mn></mrow><annotation encoding="application/x-tex">\min(3,2)=2</annotation></semantics></math>min(3,2)=2。接下来考虑 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">!</mo><msub><mo stretchy="false">)</mo><mi>b</mi></msub></mrow><annotation encoding="application/x-tex">(n!)_b</annotation></semantics></math>(n!)b 的末尾 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>0</mn></mrow><annotation encoding="application/x-tex">0</annotation></semantics></math>0 的数量。我们先枚举 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>b</mi></mrow><annotation encoding="application/x-tex">b</annotation></semantics></math>b 的因数 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>b</mi><mo>=</mo><msubsup><mi>p</mi><mn>1</mn><msub><mi>a</mi><mn>1</mn></msub></msubsup><mo>×</mo><msubsup><mi>p</mi><mn>2</mn><msub><mi>a</mi><mn>2</mn></msub></msubsup><mo>×</mo><mo>…</mo><mo>×</mo><msubsup><mi>p</mi><mi>k</mi><msub><mi>a</mi><mi>k</mi></msub></msubsup></mrow><annotation encoding="application/x-tex">b=p_1^{a_1}\times p_2^{a_2}\times \ldots \times p_k^{a_k}</annotation></semantics></math>b=p1a1×p2a2×…×pkak，若 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><msubsup><mi>p</mi><mi>i</mi><mi>m</mi></msubsup></mrow><annotation encoding="application/x-tex">p_i^{m}</annotation></semantics></math>pim 是 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>n</mi><mo stretchy="false">!</mo></mrow><annotation encoding="application/x-tex">n!</annotation></semantics></math>n! 的一个因数，则其对答案的贡献为 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mo stretchy="false">⌊</mo><mstyle displaystyle="true" scriptlevel="0"><mfrac><mi>m</mi><msub><mi>a</mi><mi>i</mi></msub></mfrac></mstyle><mo stretchy="false">⌋</mo></mrow><annotation encoding="application/x-tex">\lfloor \dfrac{m}{a_i}\rfloor</annotation></semantics></math>⌊aim⌋。<figure class="highlight cpp"><table><tr><td class="gutter"><pre>1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 </pre></td><td class="code"><pre><code class="hljs cpp">const int N=2e6+10; int n,b; int pri[N],cnt=0; int t[N]; int ans=INF; signed main() { n=read();b=read(); for(int i=2;i*i<=b;i++) { if(b%i==0) { pri[++cnt]=i; while(b%i==0) b/=i,t[cnt]++; } } if(b>1) pri[++cnt]=b,t[cnt]++; for(int i=1;i<=cnt;i++) { int nt=n; int sum=0; while(nt) { sum+=nt/pri[i]; nt/=pri[i]; } ans=min(sum/t[i],ans); } printf("%lld\n",ans); return 0; } </code></pre></td></tr></table></figure><h3 id="CF1493D-GCD-of-an-Array">CF1493D GCD of an Array</h3>由于一个集合的最大公因数的一个质因数的指数是这个集合中该质数指数的最小值，可以想到每次动态维护集合 gcd 时，考虑将 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>y</mi></mrow><annotation encoding="application/x-tex">y</annotation></semantics></math>y 分解质因数 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>y</mi><mo>=</mo><msubsup><mi>p</mi><mn>1</mn><msub><mi>e</mi><mn>1</mn></msub></msubsup><mo>×</mo><msubsup><mi>p</mi><mn>2</mn><msub><mi>e</mi><mn>2</mn></msub></msubsup><mo>×</mo><mo>…</mo><mo>×</mo><msubsup><mi>p</mi><mi>k</mi><msub><mi>e</mi><mi>k</mi></msub></msubsup></mrow><annotation encoding="application/x-tex">y=p_1^{e_1}\times p_2^{e_2}\times \ldots \times p_k^{e_k}</annotation></semantics></math>y=p1e1×p2e2×…×pkek，如果集合中除 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><msub><mi>a</mi><mi>x</mi></msub></mrow><annotation encoding="application/x-tex">a_x</annotation></semantics></math>ax 以外的其他元素均有可以对答案产生贡献的因数 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><msub><mi>p</mi><mi>i</mi></msub></mrow><annotation encoding="application/x-tex">p_i</annotation></semantics></math>pi，那么答案就可以加入 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><msub><mi>p</mi><mi>i</mi></msub></mrow><annotation encoding="application/x-tex">p_i</annotation></semantics></math>pi 产生的贡献。形式化的，如果我们定义 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><msub><mi>v</mi><mi>p</mi></msub><mo stretchy="false">(</mo><msub><mi>a</mi><mi>i</mi></msub><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">v_p(a_i)</annotation></semantics></math>vp(ai) 为 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><msub><mi>a</mi><mi>i</mi></msub></mrow><annotation encoding="application/x-tex">a_i</annotation></semantics></math>ai 中质因数 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>p</mi></mrow><annotation encoding="application/x-tex">p</annotation></semantics></math>p 的指数，那么若满足<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mi>min</mi><mo>⁡</mo><mo stretchy="false">(</mo><msub><mi>v</mi><mi>p</mi></msub><mo stretchy="false">(</mo><msub><mi>a</mi><mn>1</mn></msub><mo stretchy="false">)</mo><mo separator="true">,</mo><mo>…</mo><mo separator="true">,</mo><msub><mi>v</mi><mi>p</mi></msub><mo stretchy="false">(</mo><msub><mi>a</mi><mrow><mi>x</mi><mo>−</mo><mn>1</mn></mrow></msub><mo stretchy="false">)</mo><mo separator="true">,</mo><msub><mi>v</mi><mi>p</mi></msub><mo stretchy="false">(</mo><mi>y</mi><mo stretchy="false">)</mo><mo separator="true">,</mo><msub><mi>v</mi><mi>p</mi></msub><mo stretchy="false">(</mo><msub><mi>a</mi><mrow><mi>x</mi><mo>+</mo><mn>1</mn></mrow></msub><mo stretchy="false">)</mo><mo separator="true">,</mo><mo>…</mo><mo separator="true">,</mo><msub><mi>v</mi><mi>p</mi></msub><mo stretchy="false">(</mo><msub><mi>a</mi><mi>n</mi></msub><mo stretchy="false">)</mo><mo stretchy="false">)</mo><mo>></mo><mi>min</mi><mo>⁡</mo><mo stretchy="false">(</mo><msub><mi>v</mi><mi>p</mi></msub><mo stretchy="false">(</mo><msub><mi>a</mi><mn>1</mn></msub><mo stretchy="false">)</mo><mo separator="true">,</mo><msub><mi>v</mi><mi>p</mi></msub><mo stretchy="false">(</mo><msub><mi>a</mi><mn>2</mn></msub><mo stretchy="false">)</mo><mo separator="true">,</mo><mo>…</mo><mo separator="true">,</mo><msub><mi>v</mi><mi>p</mi></msub><mo stretchy="false">(</mo><msub><mi>a</mi><mi>n</mi></msub><mo stretchy="false">)</mo><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">\min(v_p(a_1), \ldots, v_p(a_{x-1}), v_p(y), v_p(a_{x+1}), \ldots, v_p(a_n)) > \min(v_p(a_1), v_p(a_2), \ldots, v_p(a_n))</annotation></semantics></math>min(vp(a1),…,vp(ax−1),vp(y),vp(ax+1),…,vp(an))>min(vp(a1),vp(a2),…,vp(an))设 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>A</mi></mrow><annotation encoding="application/x-tex">A</annotation></semantics></math>A 为上述两式的差值，则对答案的贡献为 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><msup><mi>p</mi><mi>A</mi></msup></mrow><annotation encoding="application/x-tex">p^A</annotation></semantics></math>pA。接下来考虑如何求。可以用线性筛预处理质数，每次操作用预处理的最小质因子分解。我们用 <code>multiset</code> 记录质数 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>p</mi></mrow><annotation encoding="application/x-tex">p</annotation></semantics></math>p 出现在的元素下标，<math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>t</mi></mrow><annotation encoding="application/x-tex">t</annotation></semantics></math>t 数组记录 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>p</mi></mrow><annotation encoding="application/x-tex">p</annotation></semantics></math>p 在多少个不同的元素中出现。当执行一次操作时，判断是否能够给答案产生贡献。如果能，那么插入当前的下标，随后暴力将 <code>multiset</code> 中的 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>1</mn><mo>∼</mo><mi>n</mi></mrow><annotation encoding="application/x-tex">1\sim n</annotation></semantics></math>1∼n 下标删除一次。<figure class="highlight cpp"><table><tr><td class="gutter"><pre>1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 </pre></td><td class="code"><pre><code class="hljs cpp">const int N=2e5+10; int n,m; int a[N]; multiset<int> st[N]; int b[N]; int prime[N]; int cnt=0; int t[N]; int ans=1; void pri(int n) { for(int i=2;i<=n;i++) { if(!b[i]) b[i]=i,prime[++cnt]=i; for(int j=1;j<=cnt;j++) { if(prime[j]>b[i] || prime[j]>n/i) break; b[i*prime[j]]=prime[j]; } } } void modify(int p,int x) { while(x!=1) { int minn=b[x]; if(st[minn].find(p)==st[minn].end()) t[minn]++; st[minn].insert(p); if(t[minn]==n) { for(int i=1;i<=n;i++) { st[minn].erase(st[minn].find(i)); if(st[minn].find(i)==st[minn].end()) t[minn]--; } ans=(ans*minn)%mod; } x/=minn; } } signed main() { pri(N-1); n=read();m=read(); for(int i=1;i<=n;i++) { a[i]=read(); } for(int i=1;i<=n;i++) { modify(i,a[i]); } while(m--) { int p=read(),x=read(); modify(p,x); printf("%lld\n",ans); } return 0; } </code></pre></td></tr></table></figure>

CF 数论做题笔记

Makerlife 的小站

Makerlife

2023年12月26日 18:46

CF1114C Trailing Loves

首先从 $10$ 进制开始分析。求 $p$ 末尾 $0$ 的数量即为求 $p$ 的因数中含有 $2$ 和 $5$ 的数量的最小值。

例如设 $x_1=2^3\times 5^2$ ，则 $x_1$ 的末尾 $0$ 的数量即为 $\min(3,2)=2$ 。

接下来考虑 $(n!)_b$ 的末尾 $0$ 的数量。我们先枚举 $b$ 的因数 $b=p_1^{a_1}\times p_2^{a_2}\times \ldots \times p_k^{a_k}$ ，若 $p_i^{m}$ 是 $n!$ 的一个因数，则其对答案的贡献为 $\lfloor \dfrac{m}{a_i}\rfloor$ 。

const int N=2e6+10;
int n,b;
int pri[N],cnt=0;
int t[N];
int ans=INF;
signed main()
{
    n=read();b=read();
    for(int i=2;i*i<=b;i++)
    {
        if(b%i==0)
        {
            pri[++cnt]=i;
            while(b%i==0) b/=i,t[cnt]++;
        }
    }
    if(b>1) pri[++cnt]=b,t[cnt]++;
    for(int i=1;i<=cnt;i++)
    {
        int nt=n;
        int sum=0;
        while(nt)
        {
            sum+=nt/pri[i];
            nt/=pri[i];
        }
        ans=min(sum/t[i],ans);
    }
    printf("%lld\n",ans);
    return 0;
}

CF1493D GCD of an Array

由于一个集合的最大公因数的一个质因数的指数是这个集合中该质数指数的最小值，可以想到每次动态维护集合 gcd 时，考虑将 $y$ 分解质因数 $y=p_1^{e_1}\times p_2^{e_2}\times \ldots \times p_k^{e_k}$ ，如果集合中除 $a_x$ 以外的其他元素均有可以对答案产生贡献的因数 $p_i$ ，那么答案就可以加入 $p_i$ 产生的贡献。

形式化的，如果我们定义 $v_p(a_i)$ 为 $a_i$ 中质因数 $p$ 的指数，那么若满足

$\min(v_p(a_1), \ldots, v_p(a_{x-1}), v_p(y), v_p(a_{x+1}), \ldots, v_p(a_n)) > \min(v_p(a_1), v_p(a_2), \ldots, v_p(a_n))$

设 $A$ 为上述两式的差值，则对答案的贡献为 $p^A$ 。

接下来考虑如何求。可以用线性筛预处理质数，每次操作用预处理的最小质因子分解。

我们用 multiset 记录质数 $p$ 出现在的元素下标， $t$ 数组记录 $p$ 在多少个不同的元素中出现。当执行一次操作时，判断是否能够给答案产生贡献。如果能，那么插入当前的下标，随后暴力将 multiset 中的 $1\sim n$ 下标删除一次。

const int N=2e5+10;
int n,m;
int a[N];
multiset<int> st[N];
int b[N];
int prime[N];
int cnt=0;
int t[N];
int ans=1;
void pri(int n)
{
    for(int i=2;i<=n;i++)
    {   
        if(!b[i]) b[i]=i,prime[++cnt]=i;
        for(int j=1;j<=cnt;j++)
        {
            if(prime[j]>b[i] || prime[j]>n/i) break;
            b[i*prime[j]]=prime[j];
        }
    }
}
void modify(int p,int x)
{
    while(x!=1)
    {
        int minn=b[x];
        if(st[minn].find(p)==st[minn].end()) t[minn]++;
        st[minn].insert(p);
        if(t[minn]==n)
        {
            for(int i=1;i<=n;i++)
            {
                st[minn].erase(st[minn].find(i));
                if(st[minn].find(i)==st[minn].end()) t[minn]--;
            }
            ans=(ans*minn)%mod;
        }
        x/=minn;
    }
}
signed main()
{
    pri(N-1);
    n=read();m=read();
    for(int i=1;i<=n;i++)
    {
        a[i]=read();
    }
    for(int i=1;i<=n;i++)
    {
        modify(i,a[i]);
    }
    while(m--)
    {
        int p=read(),x=read();
        modify(p,x);
        printf("%lld\n",ans);
    }
    return 0;
}

12 月学习笔记

Makerlife 的小站

Makerlife

2023年12月26日 18:46

CF1114C Trailing Loves

首先从 $10$ 进制开始分析。求 $p$ 末尾 $0$ 的数量即为求 $p$ 的因数中含有 $2$ 和 $5$ 的数量的最小值。

例如设 $x_1=2^3\times 5^2$ ，则 $x_1$ 的末尾 $0$ 的数量即为 $\min(3,2)=2$ 。

const int N=2e6+10;
int n,b;
int pri[N],cnt=0;
int t[N];
int ans=INF;
signed main()
{
    n=read();b=read();
    for(int i=2;i*i<=b;i++)
    {
        if(b%i==0)
        {
            pri[++cnt]=i;
            while(b%i==0) b/=i,t[cnt]++;
        }
    }
    if(b>1) pri[++cnt]=b,t[cnt]++;
    for(int i=1;i<=cnt;i++)
    {
        int nt=n;
        int sum=0;
        while(nt)
        {
            sum+=nt/pri[i];
            nt/=pri[i];
        }
        ans=min(sum/t[i],ans);
    }
    printf("%lld\n",ans);
    return 0;
}

CF1493D GCD of an Array 未完待续

形式化的，如果我们定义 $v_p(a_i)$ 为 $a_i$ 中质因数 $p$ 的指数，那么若满足

$\min(v_p(a_1), \ldots, v_p(a_{x-1}), v_p(y), v_p(a_{x+1}), \ldots, v_p(a_n)) > \min(v_p(a_1), v_p(a_2), \ldots, v_p(a_n))$

设 $A$ 为上述两式的差值，则对答案的贡献为 $p^A$ 。

接下来考虑如何求。可以用线性筛预处理质数，每次操作用预处理的最小质因子分解。

const int N=2e5+10;
int n,m;
int a[N];
multiset<int> st[N];
int b[N];
int prime[N];
int cnt=0;
int t[N];
int ans=1;
void pri(int n)
{
    for(int i=2;i<=n;i++)
    {   
        if(!b[i]) b[i]=i,prime[++cnt]=i;
        for(int j=1;j<=cnt;j++)
        {
            if(prime[j]>b[i] || prime[j]>n/i) break;
            b[i*prime[j]]=prime[j];
        }
    }
}
void modify(int p,int x)
{
    while(x!=1)
    {
        int minn=b[x];
        if(st[minn].find(p)==st[minn].end()) t[minn]++;
        st[minn].insert(p);
        if(t[minn]==n)
        {
            for(int i=1;i<=n;i++)
            {
                st[minn].erase(st[minn].find(i));
                if(st[minn].find(i)==st[minn].end()) t[minn]--;
            }
            ans=(ans*minn)%mod;
        }
        x/=minn;
    }
}
signed main()
{
    pri(N-1);
    n=read();m=read();
    for(int i=1;i<=n;i++)
    {
        a[i]=read();
    }
    for(int i=1;i<=n;i++)
    {
        modify(i,a[i]);
    }
    while(m--)
    {
        int p=read(),x=read();
        modify(p,x);
        printf("%lld\n",ans);
    }
    return 0;
}