一个脑洞

Posted by WildCow on April 12, 2018

写在前面


意外得来的一个脑洞23333

没准可以改一改出题

不过这个算是数论的一个套路吧(不)

头一次在数论题踩航神(笑)

内容


给你一个 y

求使得 $a * (y - a)$ 为平方数的 a 的数量

要求复杂度 blabala

我们令$b = y - a $

那么我们有 其中 $x^2​$ 为某个平方数(废话)

我们设 函数 $g(y)$ 为满足这个方程组的解 $a,b$ 的数量

也就是答案

然后我们尝试加强一下

如果 $d$ 不为 1,即 $a, b$ 不互质

则 $d$ 肯定是 $y$ 的因子

那么有 其中

我们设 $f(q)$ 为新的方程组的解

那么显然有 $g(y) = \sum f(y/p_i)$

其中 $p_i$ 为 $y$ 的因子

然后我们考虑怎么解下面那个方程组

互质是一个很优雅的东西

${a}’$ 和 ${b}’$ 互质

且 ${a}’ * {b}’$ 是一个平方数

那么 ${a}’$ 和 ${b}’$ 肯定也是一个平方数

所以我们枚举所有的平方数

再 check $q - {a}’$ 是不是平方数且和 ${a}’$ 互质就好了

妙啊(拍桌)