传送门

假设 $n<m$。

设 $f(x)$ 表示有多少个整点 $A,B$ 满足 $|AB|^2 <= x$ 且线段 $AB$ 之间无整点。

则答案等于 $f(h^2) - f(l^2-1)$。

那么如何计算 $f(x)$ 呢？设一条线段水平距离为 $i$，竖直距离为 $j$，那么在矩形中形如这样的线段会出现 $(n-i+1)(m-j+1)$ 次。

当线段 $(i,j)$ 可以时，$(i,-j)$ 也可以，所以上述线段的贡献为 $2$。

当线段与 $x$ 轴或 $y$ 轴垂直时，对答案贡献为 $n(m+1)+m(n+1)$。

列出 $f(x)$ 的式子

$$f(x) =(n + 1)m + m(n+1) + 2\sum_{i=1}^n \sum_{j=1}^m (n-i+1)(m-j+1) [i^2+j^2 \leq x \wedge gcd(i,j) = 1]$$

莫比乌斯反演得到

$$f(x) =(n + 1)m + m(n+1) + 2\sum_{i=1}^n \sum_{j=1}^m (n-i+1)(m-j+1) [i^2+j^2 \leq x] \sum_{d|i,d|j} \mu(d)$$

$$f(x) =(n + 1)m + m(n+1) + 2\sum_{d=1}^n \mu(d)\sum_{i=1}^{\lfloor \frac{n}{d} \rfloor} \sum_{j=1}^{\lfloor\frac{\min\{m,\lfloor\sqrt{x-i^2d^2}\rfloor\}}{d}\rfloor} (n-id+1)(m-jd+1)$$

于是枚举 $d,i$，直接计算即可，时间复杂度 $O(n\ln n)$。

#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int N = 100010;
int n, m, l, h, b;
int mu[N], vis[N], prime[N], tot;

void init() {
    mu[1] = 1;
    for (int i = 2; i < N; i ++ ) {
        if (!vis[i]) {
            prime[++ tot] = i;
            mu[i] = -1;
        }
        for (int j = 1; prime[j] * i < N; j ++ ) {
            vis[i * prime[j]] = true;
            if (i % prime[j] == 0) break;
            mu[i * prime[j]] = -mu[i];
        }
    }
}

int solve(ll x) {
    if (x <= 0) return 0;
    int ans = 0;
    for (int d = 1; d <= n; d ++ ) {
        for (int i = 1; i * d <= n; i ++ ) {
            if (1ll * i * d * i * d >= x) break;
            int lim = min(m, (int)floor(sqrt(x - 1ll * i * i * d * d))) / d, res = 0;
            res = (res + 1ll * (n - i * d + 1) * (m + 1) % b * lim % b) % b;
            res = (res + b - 1ll * (n - i * d + 1) * d % b * ((1ll * (1 + lim) * lim / 2) % b) % b) % b;
            ans = ((ll)ans + b + mu[d] * res) % b;
        }
    }
    return (1ll * n * m * 2 % b + n + m + ans * 2 % b) % b;
}

int main() {
    init();
    scanf("%d%d%d%d%d", &n, &m, &l, &h, &b);    
    if (n > m) swap(n, m);
    printf("%d\n", (solve(1ll * h * h) + b - solve(1ll * l * l - 1)) % b);
    return 0;
}