• Solved 7 out of 12 problems
• Rank 32/1041 in official records
• Solved 8 out of 12 afterwards

(√ for solved, O for upsolved, - for tried but not solved)

print(eval(input().replace('(','**(')))

考虑 $x, y$ 的质因数分解 $x = p_1^{u_1}p_2^{u_2}\dots p_n^{u_n}, y = p_1^{v_1}p_2^{v_2}\dots p_n^{v_n}$。

再回过头看答案的式子，

$$ \large\prod\limits_{i=a}^{b}\prod\limits_{j=c}^{d}\gcd(x^i,y^j)\\ \large=\prod\limits_{i=a}^{b}\prod\limits_{j=c}^{d}\gcd((p_1^{u_1}p_2^{u_2}\dots p_n^{u_n})^i,(p_1^{v_1}p_2^{v_2}\dots p_n^{v_n})^j)\\ \large=\prod\limits_{i=a}^{b}\prod\limits_{j=c}^{d}\prod\limits_{k=1}^{n}p_k^{\min(i\cdot u_k, j\cdot v_k)}\\ \large=\prod\limits_{k=1}^{n}\prod\limits_{i=a}^{b}\prod\limits_{j=c}^{d}p_k^{\min(i\cdot u_k, j\cdot v_k)}\\ \large=\prod\limits_{k=1}^{n}p_k^{\sum\limits_{i=a}^{b}\sum\limits_{j=c}^{d}\min(i\cdot u_k, j\cdot v_k)}\\ $$

考虑对每个质因数 $p_k$ 求 $$\large\sum\limits_{i=a}^{b}\sum\limits_{j=c}^{d}\min(i\cdot u_k, j\cdot v_k)$$

容易发现 $i$ 固定后 $\sum\limits_{j=c}^{d}\min(i\cdot u_k, j\cdot v_k)$ 至多由一段等差数列和一段常数列组成。

分界点是 $\lfloor\cfrac{i\cdot u_k}{v_k}\rfloor$。

那么我们枚举 $p_k$，再枚举 $i$ 即可。

这个题直接把所有 0 替换成 -1，然后对每条底边做一个左侧区域的前缀和，这个可以滚动数组维护。

然后就可以直接枚举两行作为上下底，用 bitset 直接维护中间可以作为墙的位置，然后连续段直接并起来处理。

具体处理方法：同一个块内，扫描并统计所有前缀和出现的次数。后面位置的前缀和如果是 S，那么 S-1, S, S+1 都可以与这个位置形成一个合法子矩阵，直接加进答案里就可以了。

ptw: