牛客多校3.E.Math

Analysis

首先分析题目，要求求对于给定 n n n，在 [ 1 , n ] [1, n] [1,n]范围内满足 x y + 1 ∣ x 2 + y 2 xy + 1 | x^2 + y^2 xy+1∣x2+y2的解的个数。

首先考虑合法解：要使 x y + 1 ∣ x 2 + y 2 xy + 1 | x^2 + y^2 xy+1∣x2+y2，则应满足 x 2 + y 2 = k ( x y + 1 ) x^2 + y^2 = k(xy + 1) x2+y2=k(xy+1)，则：
x 2 + y 2 = k ( x y + 1 ) x 2 + y 2 − k x y − k = 0 \begin{aligned} x^2 + y^2 = k(xy + 1) \\ x^2 +y^2 - kxy - k = 0 \end{aligned} x2+y2=k(xy+1)x2+y2−kxy−k=0​
由题意可知 1 ≤ x ≤ y ≤ n 1 \leq x \leq y \leq n 1≤x≤y≤n​​，则假设 ( x 0 , y 0 ) (x_0, y_0) (x0​,y0​)为原方程的一组合法解，那么对于方程：
x 2 + y 0 2 − k x y 0 − k = 0 x^2 +y_0^2 - kxy_0 - k = 0 x2+y02​−kxy0​−k=0
显然有一根为 x 0 x_0 x0​，此时上述方程属于一元二次方程，由韦达定理可知：
x 0 + x 1 = k y 0 ， x 0 x 1 = y 0 2 − k x 1 = k y 0 − x 0 = y 0 2 − k x 0 \begin{aligned} &x_0 + x_1 = ky_0，x_0x_1 = y_0^2 - k \\ &x_1 = ky_0 - x_0 = \frac{y_0^2 - k}{x_0} \end{aligned} ​x0​+x1​=ky0​，x0​x1​=y02​−kx1​=ky0​−x0​=x0​y02​−k​​
很显然， ( k y 0 − x 0 , y 0 ) (ky_0 - x_0, y_0) (ky0​−x0​,y0​)为满足原方程的一组解。且 k y 0 − x 0 ≥ 0 ky_0 - x_0 \geq 0 ky0​−x0​≥0，那么最小的一组整数解满足 k y − x = 0 ky - x = 0 ky−x=0​

那么打表可以发现，每条解(自下述 1 1 1形式开始向后)呈现以下规律：

1. x 0 = a 3 x_0 = a^3 x0​=a3
2. s i + 1 = s i × a 2 − s i − 1 s_{i + 1} = s_i \times a^2 - s_{i- 1} si+1​=si​×a2−si−1​

那么预处理全部答案，二分查找询问即可。

#include 
#define int long long
#define mod 1000000007
#define N 100005
using namespace std;
int n, d, a1, a2, t, sum, tot;
int a[1000] = {8, 30};
struct node{
    __int128 x, y;
    bool operator