_皎月半洒花 的博客

_皎月半洒花 的博客

反抗命运的镇魂曲停歇之前,你绝对不可以说我懦弱,绝对不可以说我没有殊死一搏。

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

posted on 2019-08-13 13:23:32 | under 题解 |

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

下文中用 $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 ;
}