枚举分隔的位置，左边的一起向左，右边的一起向右。统计答案即可。
看了WJMZBMR的代码才明白过来T_T，容斥太弱了。算出区间内每个数包含的素因子。然后因为要gcd变为1，所以可以看成不能包含素因子Pi这若干个条件的与。接着就可以用容斥原理了。
看了芒果的代码才明白过来。首先是不能一行一行来填，这样dp的状态太难表示。
然后考虑一列一列来填。
- 假如只有left的话，就可以f[i][j]来表示填好前i列，其中有j列还没分配的时候的方案数。然后这个j其实蕴含了前面有j列是要填东西的，但是还没决定填在哪些行这么个意思。然后遇到left的结束端点，就可以拿这些数目去分配。大致就是乘个A几几的组合数。
- 现在如果有right的话，可以按left反过来那样处理，但是现在要统一起来，只能考虑从左往右填。由于一个行进入可填范围就不会变没了，所以f[i][j]表示填好前i列，还有j行没搞定。于是每次可以选择(或者不选)一个行，用当前列来填上。
- 最后把前两种dp合起来，f[i][j][k]转移一下就好了。