这道题直接暴力枚举

因为这个图的左右是对称的，我们可以只考虑所有斜率>0的线段：根据这条，我们可以分出当线段与水平/竖直方向平行的情况来。显然，只有全部长度为1的线段满足要求，此时如果1在[L,R][L,R]内，则需要加上这些情况。

我们还可以算出一个格点图内与当前枚举的线段相同的线段个数：将这条线段视作与横竖直线构成了一个Rt△Rt△，那么问题可以转化为求在格点图中与该Rt△Rt△相同的个数，这个只需要O(1)O(1)即可完成（对于直角边分别为x,y的Rt△Rt△，在纵方向上有(n-x+1)种可能性，在横方向上有(m-y+1)种可能性，根据乘法原理得到个数），所以重点是在枚举不同的Rt△Rt△。

通过分析两个条件，我们可以知道一个符合要求的Rt△Rt△（设直角边分别为x,y）必须满足： L2≤x2+y2≤R2，gcd(x,y)=1。

Code

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cmath>
using namespace std;
int read(){
    long long a=0,k=1;char c=getchar();
    while (!isdigit(c)){if (c=='-')k=-1;c=getchar();}
    while (isdigit(c)){a=a*10+c-'0';c=getchar();}
    return a*k;
}
long long ans,n,m,l,r;
int gcd(int a,int b){ 
    if (a==0)return b;
    return gcd(b%a,a);
}
int main(){
    n=read();m=read();l=read();r=read();
    if(l==1){ans=ans+(n+1)*m+(m+1)*n; }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            double now=sqrt(i*i+j*j);
            if(now<l||now>r||gcd(i,j)!=1)continue;
            ans=ans+2*(n-i+1)*(m-j+1);
        }
    }
    printf ("%lld\n",ans);
}

求管理员通过（QWQ）

#include <bits/stdc++.h>
using namespace std;
int n, m, l, r;
long long ans;
int gcd(int a, int b) {
    return a % b == 0 ? b : gcd(b, a % b);
}
int main(void) {
    scanf("%d%d%d%d", &n, &m, &l, &r); 
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            if(gcd(i, j) == 1 && i*i + j*j >= l*l && i*i + j*j <= r*r)
                ans += 2 * (n - i + 1) * (m - j + 1);
    if(l == 1) ans += n * (m + 1) + (n + 1) * m;
    printf("%lld\n", ans);
    return 0;
}