题解 P2997 【[USACO10NOV]Banner S】

· · 题解

这道题直接暴力枚举

因为这个图的左右是对称的，我们可以只考虑所有斜率>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）