CVBB ACM Team

本页面只读。您可以查看源文件，但不能更改它。如果您觉得这是系统错误，请联系管理员。

===== 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$ 个，对每个询问二分查询。

CVBB ACM Team

用户工具

站点工具

页面工具