题解 CF1202F 【You Are Given Some Letters...】

· · 题解

Σ( ° △ °|||)︴啊嘞，为什么这么好一道题没人做啊。

下文中用a,b表示输入的那俩值。

我们考虑对于一个合法的k而言，假设在这个k满足k=\lfloor n/p\rfloor,p\in \mathbb{N}，那么p就是循环节的数量。现在我们假设有q_a+q_b=k，即每一段循环节中A的数量和B的数量。那么一定需要满足的是q_a\cdot p\leq a并且q_b\cdot p\leq b。

看上去有了这个之后我们就可以直接数了？我们考虑一定需要的是

q_a \leq \lfloor\frac{a}{p}\rfloor, q_b \leq \lfloor\frac{b}{p}\rfloor

但同时也要注意，还有一个条件，就是我们的p既然是循环节的数量，并且我们实际上可以多出去一堆下脚料（雾，那么也就是说剩下的字符数量a_{rest},b_{rest}必须小于等于我们的q_a和q_b。也就是说需要有

(p+1)\cdot q_a \geq a,(p+1)\cdot q_b\geq b

美化一下就是

\lceil \frac{a}{p+1} \rceil \leq q_a\leq \lfloor \frac{a}{p} \rfloor \lceil \frac{b}{p+1} \rceil \leq q_b\leq \lfloor \frac{b}{p} \rfloor

那么我们就可以通过从1到n枚举p来求得q_a和q_b，那么根据上文的定义，q_a和q_b是单独一段循环节中的A和B的数量，所以q_a+q_b对k产生贡献。

然后这东西显然是可以数论分块的，所以我们分一下块就做完了：

#define LL long long
#define Mod 1000000007

using namespace std ;
int N, M, L ; LL Ans ;

int main(){
    cin >> N >> M, L = N + M ;
    for (int g, l = 1, r ; l <= L ; l = r + 1){
        g = L / l, r = L / g ;
        if (N < g || M < g) continue ;
        int ln = (N + g) / (g + 1), hn = N / g ;
        int lm = (M + g) / (g + 1), hm = M / g ;
        if (hn >= ln && hm >= lm)
            Ans += max(0ll, 1ll * (min(hn + hm, r) - max(l, lm + ln) + 1)) ;
    }
    cout << Ans << endl ; return 0 ;
}