题目link
学习博客
a
i
2
+
a
j
=
x
2
a_i^2+a_j=x^2
ai2+aj=x2
移项得:
a
j
=
x
2
−
a
i
2
a_j=x^2-a_i^2
aj=x2−ai2
平方差公式得:
a
j
=
(
x
+
a
i
)
(
x
−
a
i
)
a_j=(x+a_i)(x-a_i)
aj=(x+ai)(x−ai)
可以发现
a
j
a_j
aj 为其两个因子的乘积且满足
(
x
+
a
i
)
−
(
x
−
a
i
)
=
2
∗
a
i
(x+a_i) - (x-a_i) = 2*a_i
(x+ai)−(x−ai)=2∗ai
1
e
6
1e6
1e6范围内数因子个数最多量级为
4000
4000
4000
那么可以枚举因子
利用短除法求因子
O
(
n
∗
n
)
O(n*\sqrt{n})
O(n∗n
)可能会T,这里利用倍增
O
(
n
∗
l
o
g
(
n
)
)
O(n*log(n))
O(n∗log(n))求因子
for(int i = 1;i <= 1000000;i++) for(int j = i;j <= 1000000;j+= i) // 第一层枚举一个因子 i , j/i为第二个因子,乘积为j
int n; int a[1000005]; int cot[1000005]; signed main() { _orz; cin>>n; forr(i,1,n) cin>>a[i],cot[a[i]]++; int res = 0; // 倍数取因子; // 会出现两次 例如: i = 1 j = 3 // i = 3 j = 3 // for(int i = 1;i <= 1000000;i++){ for(int j = i;j <= 1000000;j+= i){ int mi = min(j/i,i),ma = max(j/i,i); int d = ma-mi; if(d%2==0){ res += cot[j]*cot[d/2]; // if(cot[j] && cot[d/2]) // cout << j <<" "<< d/2 << endl; } } } cout << res/2 << '\n'; return 0; }