G. Math Test
对不起，我数学太差了。
题目大意：给定 $1\le a\le10^{5}$ 和 $1\le n\le10^{18}$，求有多少 $1\le x\le y\le n$ 满足 $\gcd(x,y)=1$，$x\mid y^{2}+a$，$y\mid x^{2}+a$。有 $10^{6}$ 组询问。
题解：对于一组满足要求的 $x,y$，可以证明 $y,\frac{y^{2}+a}{x}$ 也满足要求。
$$ \begin{aligned} &\left(\frac{y^{2}+a}{x}\right)^{2}+a\\ =&\frac{y^{4}+2ay^{2}+a^{2}+ax^{2}}{x^{2}}\\ =&\frac{y^{4}+2ay^{2}+a(x^{2}+a)}{x^{2}} \end{aligned} $$
显然能被 $y$ 整除。假设质数 $p$ 满足 $p\mid y,p\mid\frac{y^{2}+a}{x}$，那么 $p\mid a$。又 $y\mid x^{2}+a$，因此 $p\mid x$，矛盾。因而 $\gcd(y,\frac{y^{2}+a}{x})=1$。
反过来，$\frac{x^{2}+a}{y},x$ 也满足要求。容易发现这两个变换互为逆变换。显然 $y\le\frac{y^{2}+a}{x}$ 仍然成立，而逆变换则不一定成立。我们显然每个合法的对一直逆变换，直到 $\frac{x^{2}+a}{y}>x$ 为止。所有合法对都可以通过这样的对变换得到。
要使 $x\le y$，而 $\frac{x^{2}+a}{y}>x$，那么就有 $x(y-x)<a$。那么这样的 $x,y$ 对只有 $a\log a$ 个。然后 $a$ 则解个同余方程即可，合法的 $x,y,a$ 对约两百多万个。于是我们可以把全部表打出来，这个数字应该是 $19491555$ 个，对每个询问二分查询。
