#P11701. [ROIR 2025] 平方差

    ID: 13061 远端评测题 1000ms 512MiB 尝试: 0 已通过: 0 难度: 3 上传者: 标签>数学2025Special JudgeROIR(俄罗斯)

[ROIR 2025] 平方差

题目背景

翻译自 ROIR 2025 D2T1

题目描述

给定 llrrdd,求有多少个自然数对 (x,y)(x,y) 满足 ly2<x2rl \leq y^2 < x^2 \leq rx2y2=dx^2-y^2=d

输入格式

输入三个整数 ddllrr1d1091 \leq d \leq 10^91lr10181 \leq l \leq r \leq 10^{18})。

输出格式

输出满足条件的 (x,y)(x,y) 的数量。

64 1 100
1
64 1 300
2

提示

样例解释:

在第一个样例中,符合条件的数对是 (10,6)(10,6)
在第二个样例中,符合条件的数对还有 (17,15)(17,15)%loj 上样例解释有误

本题使用 Subtask 捆绑测试。数据中 Subtask 0 是样例。

子任务 分数 特殊性质
11 18 18 1d1031 \leq d \leq 10^3, 1lr1031 \leq l \leq r \leq 10^3
22 1919 1d1051 \leq d \leq 10^5, 1lr1051 \leq l \leq r \leq 10^5
33 2020 1d1071 \leq d \leq 10^7, 1lr1071 \leq l \leq r \leq 10^7
44 2121 1d1091 \leq d \leq 10^9, 1lr10101 \leq l \leq r \leq 10^{10}
55 2222