A. 神炎皇

很好的一道题，可能第一次在考场上遇到欧拉函数

题意：对于一个整数对 $(a,b)$，若满足 $a\times b\leq n$且$a+b$是$a\times b$的因子，

则称为神奇的数对。问这样的数对共有个？

首先式子同时除一个$gcd(a,b)$,那么设$d=gcd(a,b)$,则$a=A/d,b=B/d$,

 所以因为$a$,$b$,中已经将因子全部提出，所以$a\times b$与$a+b$是互质的

然后设$k$为$d/(a+b)$，显然$k\times (a+b)\times (a+b)\leq n$

因此$k\leq n/(x\times x)$

同时对于$a+b$我们只需枚举到$\sqrt{n} $即可

那么考虑范围，对于每个枚举的$i=a+b$,那么显然$k$的取值是$n/(i*i)$,

然后对于$i$我们可以求出$\varphi {i}$，

因为$a+b=i$,所以对于每个与$i$互质的数$x$可得$gcd(i,x)==1$,即

$gcd(i-x,x)==1$。

 时间复杂度$O(\sqrt{n} )$.