2022.3.21 代码源每日一题div1 #607. 平方计数

由 \(a[i]^2 + a[j] = x^2\)
移项可得：\(a[j] = x^2-a[i]^2 = (x-a[i])*(x+a[i])\)
可见：\(x-a[i]\)与\(x+a[i]\)均为\(a[j]的因子\)
设\(fac_1 = x-a[i], fac_2=x+a[i]\)
观察可以得到：\(fac_2-fac_1=2*a[i]\)
所以我们可以枚举两个\(a[j]\)的因子\(fac_1,fac_2\)
判断两个因子相减是否等于\(2*a[i]\)，统计答案即可
注意枚举的时候不能从\(1\)到\(sqrt(n)\),\(O(n\sqrt n)\)会T
用类似筛素数的方法枚举引子即可，复杂度为\(O(n\log n)\)
注意，任何一对因子\(fac_1\)与\(fac_2\)均会被枚举两次，所以答案要除\(2\)

#include
#include
#include
#include
#include
#include
#include
#include
#define x first
#define y second
#define ll long long
#define pii pair 
#define mp(a, b) make_pair(a, b)
#define rep(i, a, b) for(int i = a; i <= b; ++i)
#define per(i, a, b) for(int i = a; i >= b; --i)
#define clr(a, b) memset((a),b,sizeof(a))
using namespace std;
inline int read(){
	int s = 0, w = 1; char ch = getchar();
	while(ch < '0' || ch > '9')   { if(ch == '-') w = -1; ch = getchar(); }
	while(ch >= '0' && ch <= '9') { s = (s << 3) + (s << 1) + (ch ^ 48); ch = getchar(); }
	return s * w;
}
const int N = 1e6 + 50;
int n, a[N], ans; 
int main() {
	n = read();
	rep(i, 1, n) {
		a[read()] ++;
	}
	rep(i, 1, 1000000) {
		for(int j = i; j <= 1000000; j += i) {
			int minn = min(j / i, i);
			int maxn = max(j / i, i);
			int d = maxn - minn;
			if(d % 2 == 0) {
				ans += a[j] * a[d / 2];
			}
		}
	}
	cout << ans / 2;
	return 0;
}