10 pts

没啥好说的，暴力就完了，可能 $i^j$ 比较大，用 hash 或者其他什么方法处理一下就好了。

30 pts

先考虑哪些数可能会产生重复。

对于第 $x$ 行，显然只有第 $x^2,x^3...x^k$ 行上的数可能与它有重复。

考虑去计算这个东西，设 $f_k$ 表示对应的答案。

问题转化为 $i\in [1,k],j\in [1,m]$，求 $ij$ 有多少个不同的取值。

由于 $k$ 是 $\log n$ 级别的，可以直接暴力枚举，然后枚举 $x$ 就做完了。

时间复杂度 $O(m\log n+n)$。

代码可以看附加文件中的 brute force.cpp。

60 pts

这档分是白给的，知道上面的结论后，可以发现当 $x>\sqrt{n}$ 时显然 $k=1$。

转换一下，令 $g_k=km-f_k$，这个同样也可以暴力求，那么答案只需要减掉 $x\le \sqrt{n}$ 的就好了。

时间复杂度 $O(m\log n+\sqrt{n})$。

100 pts

依然考虑计算 $g_k$，考虑如何更快计算。

分开计算，考虑在 $( (p-1)m,pm ]$ 上有多少个不同的取值。

对这个区间产生贡献的显然 $i\ge p$。

比较容易想到容斥，枚举一下选那些数，令这些数的 Lcm 为 $L$，那么对应的答案就是 $r/L-l/L$，乘上个容斥系数就好了。

但会发现暴力枚举时间复杂度是 $O(2^{\log n})=n$，依然爆炸。

考虑如果我选择 $i$，那么 $2i,3i...$ 在这个区间中的数必然包含在 $i$ 中。

所以可以把每个数的倍数减掉。

$30$ 以内这样可以减掉许多数，最后剩下来的数稳定在 $10$ 个左右。

所以就快速求出了 $g_k$ ，总时间复杂度 $O(2^{10}\log^2 n+\sqrt{n})$。

代码可以看附加文件中的 std.cpp。