题解：P11701 [ROIR 2025] 平方差

wzb13958817049 · 2025-02-10 21:44:42 · 题解

思路

由题目标题的提示不难想到平方差公式 x^2 - y^2 = ( x + y ) \times ( x - y )，可知枚举的 x + y 和 x - y 都是 d 的因数，所以我们可以枚举 d 的因数从而达到 O(\sqrt{d})。

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll l,r,d,ans;
int main(){
    ios::sync_with_stdio(0),cout.tie(0),cin.tie(0);
    cin>>d>>l>>r;
    for(int i=1;i*i<=d;i++){
        if(d%i==0){
            //x+y=i x-y=d/i;
            if((i+d/i)%2==0){
                ll x=(i+d/i)/2;
                ll y=x-i;
                if(y*y<x*x && l<=y*y && x*x<=r) ans++;
            }
        }
    }
    cout<<ans;
    return 0;
}