A. [NOIP 2023 模拟赛五 By FXT A] 简单数学题

summarization

给出一个值域为 \([1,m]\) 的正整数序列 \(a_{1\sim n}\)，序列中的数各不相同，求出使 \(a_i^2+a_j\) 为完全平方数的 \((i,j)\) 的对数。

solution

实际上就是求 \(x^2+y=z^2\quad(x,y,z\in\mathbb{N}^+)\) 的 \((x,y)\)，其中 \(x,y\) 需要在序列中存在。

变形为 \(y=(z+x)(z-x)\)，考虑 \(y\) 的所有成对因数。

枚举 \(y\)，分解 \(y=a\times b\quad(a<b,a,b\in\mathbb{N}^+)\)，根据 \(z+x=b,z-x=a\)，求出 \(z,x\)，最后统计答案。

由于枚举 \(y\) 太慢，考虑枚举因数 \(i\)，再枚举 \(i\) 的倍数 \(ki\quad(k\ge2,ki\le m,k\in\mathbb{N}^+)\)

code

CI N = 1e6; int n, m, Tng[N + 5];
int main () {
	RI i, j; for (Read (n, m), i = 1; i <= n; ++ i) {int x; Read (x); ++ Tng[x];}
	ll ans = 0; for (i = 1; i <= N; ++ i) for (j = i; j <= N; j += i) {
		int minn = min (i, j / i), maxx = max (i, j / i); if ((maxx - minn) % 2 == 0) ans += Tng[j] * Tng[(maxx - minn) / 2];
	} ans /= 2; printf ("%lld\n", ans);
	return 0; 
}