跟着**w刷水题

### [lao_wang](https://www.luogu.com.cn/user/701408)先生，是一位十分【数据删除】的整体二分使用者及发扬者。 ### 对此，我对这位伟大的lao_wang先生，写了一本《_____王传》 ------------ # 第一卷：数论 ## 整除分块： lao_wang先生在没有接触整体二分的早年，对于一些基础数论较感兴趣。一天，作者我用整除分块算法AC了一题，从此lao_wang开始了他【数据删除】的人生。 - ### [lao_wang先生学习过的资料](https://oi-wiki.org/math/number-theory/sqrt-decomposition/) 一言以蔽之：对于形如 $$\sum_{i = 1}^n f(i)\lfloor \frac{m}{i} \rfloor$$ 的柿子可以 $O(\sqrt n)$ 计算 好了，想必你已经学会了 ## 赶快去do一下题单的第一题，多么的简单 __[题目在这](https://www.luogu.com.cn/problem/AT_abc230_e)__ ————————唐氏儿分界线———————— ------------ do完了吗，是不是非常的板子 ## 那么直接上难度，体验蓝题的压迫感 __[题目在这](https://www.luogu.com.cn/problem/P2261)__ #### 别去看题解，给你个提示（其实就是题解上说的）： $$k\mod i = k-i*\lfloor \frac{k}{i} \rfloor$$ #### 知道了这个，这个蓝题就变得多~~么的简单啊 #### 如果你不知道旁边那个 $i$ 该怎么处理，我再提示下。 ### 上一题代码中的一行： ```cpp ans+=(k/l)*(r-l+1); //记boki(i)为f(1)~f(i)的和 // k/l就要去乘以此时（boki(r)-boki(l-1)) ``` 前面那题，$f(i)=1$ ,所以他乘的数就是$ r-l+1 $ ，是不是？没问题吧。 这一题你发现 $f(i)=i$ ,所以他的前缀和也要改一下，改成等差数列。 ————————唐氏儿分界线———————— ------------ 好了，相信你遗精AC了这道题 ## let us看下一题 __[题目在这](https://www.luogu.com.cn/problem/P3935)__ 这题有点阴间，我不会化柿子只能看题解 就是给你 $l,r$，求出$\large{\sum\limits_{i=1}^r ⌊\frac{r}{i}⌋} - \large{\sum\limits_{i=1}^{l-1} ⌊\frac{l-1}{i}⌋}$ 化出来了，你看，多么的板子啊。啊但是！__注意取模__。 ————————唐氏儿分界线———————— ------------ ## 本章boss：[[清华集训2012] 模积和](https://www.luogu.com.cn/problem/P2260) 一看名字就有很强的压迫感 当时，lao_wang先生鏖战了三天三夜才AC了这道题，我作为见证人，十分的有感触，因为我也花了这么久来做。 进入正题，首先看柿子，根据前面题目的经验，你应该知道这个 $mod$ 该怎么搞。 ### 给几个提示（也可以看题解）： - $\large{\sum\limits_{i=1}^n 114} * \large{\sum\limits_{j=1}^m 514} =\large{\sum\limits_{i=1}^n \sum\limits_{j=1}^m 114*514}$ - 那个 $i≠j$ 用容斥搞 - 最后的一个地方要用到二维整除分块，模板如下： ### 求 $\large{\sum\limits_{i=1}^k ⌊\frac{n}{i}⌋⌊\frac{m}{i}⌋}$ 的代码： ```cpp for(int l=1,r;l<=k;l=r+1){ r=min(min(n/(n/l),m/(m/l)),k); ans+=(boki(r)-boki(l-1))*(n/l)*(m/l); } //此处boki(i)与前面提到的一致，是前缀和 ``` - 如果打出来之后因取模而WA，可以看[这篇帖子](https://www.luogu.com.cn/discuss/569718) 整除分块完结 ------------ ------------ ## BSGS： lao_wang先生在寒假学习期间，对于伟大的CYJian老师所讲解的BSGS算法十分感兴趣，并且认认真真的开始做BSGS题。 ### 去看下板子题的题解你就懂过程了 __[【模板】BSGS](https://www.luogu.com.cn/problem/P3846)__ 一言以蔽之：对于形如 $ a^x \equiv b \pmod {p} $ 的柿子，BSGS算法可以 $O(\sqrt p)$ 求出 $x$ 的最小非负整数解。（前提条件是 $a$ 与 $p$ 互质） ### 注意看，这是我见过最短的BSGS代码： ```cpp map<int,int> d; int bsgs(){ b%=k; if(b==1) return 0; //注意看题目，如果要求“最小正整数”而不是“最小非负整数”就把返回0的特判删了 int t=ceil(sqrt(k)); for(int i=0,x=b;i<t;i++,x=x*a%k) d[x]=i; //f()函数为快速幂 for(int i=1,y=f(a,t,k),x=y;i<=t;i++,x=x*y%k) if(d.count(x)) return i*t-d[x]; return -1; } ``` ————————唐氏儿分界线———————— ------------ ## 首先来道煎蛋题：__[多少个 1？](https://www.luogu.com.cn/problem/P4884)__ 别看它是一道紫题，实际上它就只有紫题难度。 考虑把左边那堆 $111111...$ 转成 $a^x$ 形式 相信聪明的你一定可以想到的 ## 思考时间 | | | | | 没错，就是$\frac{10^x-1}{9}$。你看，多么的智慧啊。移项一下就变成了$ 10^x\equiv 9K+1 \pmod m$，然后BSGS直接求就行了。 还有，__本题要用int128__。知道你懒，代码给你 ```cpp #define int __int128 int read(){ int x=0; char c=getchar(); while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar(); return x; } void print(int x){ if(x>10) print(x/10); putchar(x%10+'0'); } ``` ————————唐氏儿分界线———————— ------------ ## 好了，休息一下吧，做个板子题好不好 __[题目在这](https://www.luogu.com.cn/problem/P4028)__ 本题就是多组数据的BSGS。 但是这题有几个很构式的地方需要注意： - $B=1$ 时，要输出 $0$ - 如果 $A$ 与 $P$ 不互质且 $B≠0$，此时无解，因为不满足BSGS的前提条件。 然后就没了 ### 但是！你以为这就是一个普通的题目吗！ ### 你错了！ ### 这道题，有我们伟大的lao_wang所贡献的[题解](https://www.luogu.com.cn/article/27zohe19)! 必须去看一下 ————————唐氏儿分界线———————— ------------ ## 又一道板子题 __[题目在这](https://www.luogu.com.cn/problem/P2485)__ 本题就是缝合了三个算法：快速幂，扩展欧几里得，BSGS 没啥好说的直接去do罢。 知道你懒，扩欧模板题 __[在这](https://www.luogu.com.cn/problem/P1082)__ 扩欧判无解很简单，答案算出来为 $0$ 就是无解 ————————唐氏儿分界线———————— ------------ ## 第三道板子题： [[CQOI2018] 破解D-H协议](https://www.luogu.com.cn/problem/P4454) 一看题面直接给我吓立了，实际上就是连续让你求两个 $ a^x \equiv b \pmod {p} $ 的最小正整数解，记作 $x_1$ 与 $x_2$ ，再输出$ g^{x_1 * x_2} \mod p $ 就完了 ————————唐氏儿分界线———————— ------------ ## 变异版：exBSGS [【模板】扩展 BSGS/exBSGS](https://www.luogu.com.cn/problem/P4195) 它这个变异法就是，给你的 $a$ 和 $p$ 不一定互质 然后你可以经过神奇的逆元把柿子变得互质，然后跑普通bsgs 过程见 __[题解](https://www.luogu.com.cn/problem/solution/P4195)__ ，第一篇可能有点阴间，可以看后面几篇的证明过程 然后我给个板子 ```cpp a%=k,b%=k;//开局取模 if(b==1||k==1){ //当b或k等于1时显然最小解为0 （此处k为模数） cout<<"0\n"; return; } tot=1,cnt=0;//tot统计a/d的积 while((g=__gcd(a,k))!=1){ //重复操作直到ak互质 if(b%g){ //b必须时刻整除gcd(a,k)，否则柿子无解 cout<<"No Solution\n"; return; } b/=g,k/=g;//两边除 tot=tot*(a/g)%k,++cnt;//加次数，统计tot if(b==tot){ //此时若b和tot相等直接输出cnt cout<<cnt<<'\n'; return; } } int x,y; exgcd(tot,k,x,y);init=(x%k+k)%k; b=b*init%k;//b除以tot，但是不能直接除，要求逆元 ``` 后面正常BSGS就行。 ### [双倍经验 MOD - Power Modulo Inverted](https://www.luogu.com.cn/problem/SP3105) BSGS完结 ------------ ------------ # 第二卷：离线算法 ## CDQ分治： CDQ 分治的思想最早由 IOI2008 金牌得主陈丹琦在高中时整理并总结，它也因此得名。后来，大神lcrh在讲课时提到这个算法，lao_wang也因此学会CDQ分治，为接下来学习整体二分奠定了基础。 TLHLL懒得写 ------------ ------------ ------------ ## 整体二分：  $ 整体二分哪家强，CQYC \color{white}{jyw}$。 ------------ ------------ ------------ ------------ ------------ ------------ ------------ ------------ ------------ ------------ ------------ ## 前置芝士：[萎大的牢王的博客](https://blog.csdn.net/Yale_dd/article/details/138281672?csdn_share_tail=%7B%22type%22%3A%22blog%22%2C%22rType%22%3A%22article%22%2C%22rId%22%3A%22138281672%22%2C%22source%22%3A%22Yale_dd%22%7D)（不用做题，看下整体二分的思想和代码就行） 整体二分这个算法我感到非常的抽象，具体他这个抽象是抽象在哪，诶，你看他这个变量，一般是 $l,r,k,id,op$ 这些玩意对吧。但是这个 [$ op $](https://www.yuanshen.com) 一变，他的其他变量意义基本全变了，就这点，我在自己看整体二分题解的时候，大家写得千奇百怪啊，我tm是一点都看不懂。为了很好的解决这个问题，我创造了一种 **“唐氏整体二分法”** 。那就是我对于操作类型不同，为两种类型单独创一堆变量。虽然在整体二分之外看起来很臃肿，啊但是别人或者你自己看这个代码，看起来就有很好的可读性。 ------------ 比如静态区间第 $k$ 小问题： **[【模板】可持久化线段树 2](https://www.luogu.com.cn/problem/P3834)** 牢王的博客里没有对这些变量进行一些解释，导致劳资看了很久。可能是我理解能力太差，但是有了我的**唐氏整体二分法**，代码就变得多么的美丽啊。 ### [我的代码（内有注释）](https://www.luogu.com.cn/paste/fahtityo) || [本题双倍经验 P1533](https://www.luogu.com.cn/problem/P1533) ————————唐氏儿分界线———————— ------------ 然后是动态区间第 $k$ 小问题： **[Dynamic Rankings](https://www.luogu.com.cn/problem/P2617)** ### [我的代码（内有注释）](https://www.luogu.com.cn/paste/dff97eib) ————————唐氏儿分界线———————— ------------ 直接来一道紫题： **[[国家集训队] 矩阵乘法](https://www.luogu.com.cn/problem/P1527)** 本题要用一个二维树状数组，不知道写法的可以看lao_wang博客 ### [我的代码（内有注释）](https://www.luogu.com.cn/paste/bq8jhuzr) ————————唐氏儿分界线———————— ------------ 然后是《天天爱蛇精》： **[[THUPC2017] 天天爱射击](https://www.luogu.com.cn/problem/P7424)** 本题先考虑一个一个二分怎么搞，再转化到整体二分。 本题有个究极唐氏问题：一般题的树状数组的修改都是$(x<=n)$，但是这个题目它的 $n$ 是木板数量，而我们树状数组是装坐标的，所以本题要改成$(x<=2e5)$ ($2e5$为坐标的最大值) ### [我的代码（内有注释）](https://www.luogu.com.cn/paste/gxpdwpiw) ————————唐氏儿分界线———————— ------------ 下一题：**[[POI2011] MET-Meteors](https://www.luogu.com.cn/problem/P3527)** 和上一题一样，本题先考虑一个一个二分怎么搞，再转化到整体二分。可以想到二分第 $i$ 个国家多久能完成收集任务，然后直接开写。还有，这题很应当，buff叠满： - 必须用int128。 - 断环为链 - 离散化 ### [我的代码（内有注释）](https://www.luogu.com.cn/paste/61zwfyks) ————————唐氏儿分界线———————— ------------ 奖励关：**[[ZJOI2013] K大数查询](https://www.luogu.com.cn/problem/P3332)** 就是两个操作，一个在 $l,r$ 每个位置插入一个 $k$ ,一个询问 $l,r$ 第 $k$ **大**。 然后不难发现这就是之前的动态区间第 $k$ 小问题的升级版 把树状数组换成线段树即可。 ### [我的代码（内有注释）](https://www.luogu.com.cn/paste/ibb7iypc)