CodeForces - 1202F You Are Given Some Letters... (整除分块)

题意：一个字符串包含a个A和b个B，求这个字符串所有可能的循环节长度（末尾可能存在不完整的循环节）

好题，但思路不是很好想。

首先由于循环节长度可以任意取，而循环次数最多只有$O(\sqrt n)$个，因此考虑枚举循环次数（利用整除分块的思想），求a,b可能的循环长度。

那么问题转化成了：给定最大循环次数k和字符个数n，求循环长度l的取值范围，也就是使得$\left \lfloor \frac{n}{l}\right \rfloor=k$的l的取值范围。

首先确定l的上界，即$kl\leqslant n$，$l\leqslant \left \lfloor \frac{n}{k}\right \rfloor$，这个是显然的。

然后确定l的下界，如果$kl+l\leqslant n$的话，那么可以再分出去一个l，与最大循环次数为k矛盾，因此下界为$(k+1)l>n$，$l\geqslant\left \lfloor \frac{n}{k+1}\right \rfloor+1$。

综上，l的取值范围应为$[\left \lfloor \frac{n}{k+1}\right \rfloor+1,\left \lfloor \frac{n}{k}\right \rfloor]$。

然后貌似对于每个最大循环次数k，令n分别等于a,b，求出a和b的取值范围，进而确定a+b的取值范围就可以了。

但是这里有一个问题：a和b的k值不一定相等！比如说有10个a，9个b，每段有2个a和2个b，那么a和b的k值分别为5和4！（坑死人）

于是只能允许$kl+l=n$的情况存在了，也就是强行令$(k+1)l\geqslant n$，即$l\geqslant \left \lceil \frac{n}{k+1}\right \rceil=\left \lfloor \frac{n+k}{k+1}\right \rfloor$，这样就能应付上面的特殊情况了。

然而这样还没完，求出的取值范围可能有重复！怎样去重呢？最无脑的方法是把所有取值范围的区间排个序然后从左往右扫一遍，不过也可以限制一下l的取值范围，也就是强行令$l\in [\left \lfloor \frac{a+b}{k+1}\right \rfloor+1,\left \lfloor \frac{a+b}{k}\right \rfloor]$，这样就能避免重复了。

逻辑可能不是很清晰，如果还不明白的话可以去看官方题解

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const int N=1e5+10,inf=0x3f3f3f3f;
 5 int a,b;
 6 int main() {
 7     scanf("%d%d",&a,&b);
 8     int ans=0;
 9     for(int l=1,r,k; l<=a+b; l=r+1) {
10         k=(a+b)/l,r=(a+b)/k;
11         int L1=(a+k)/(k+1),R1=a/k;
12         int L2=(b+k)/(k+1),R2=b/k;
13         if(L1<=R1&&L2<=R2)ans+=min(R1+R2,r)-max(L1+L2,l)+1;
14     }
15     printf("%d\n",ans);
16     return 0;
17 }

CodeForces - 1202F You Are Given Some Letters... (整除分块)

原文：https://www.cnblogs.com/asdfsag/p/11704245.html